On the representation and multiplication of basic alternating cycle matrices
Dr. Paulus Gerdes
Abstract In the
following paper the circular representation of basic positive and basic
negative alternating cycle matrices is determined. This representation
enables the calculation of the multiplication tables of basic positive
and basic negative alternating cycle matrices. Surprisingly, the associated
matrices of these multiplication tables are alternating cycle matrices
themselves. Several further properties are derived. The multiplication
of positive and negative alternating cycle matrices follows the rule of
signs of the multiplication of positive and negative numbers. The multiplication
of positive alternating cycle matrices is commutative. The multiplication
of negative alternating cycle matrices is symmetrical.
Basic alternating cycle matrices Any positive alternating cycle matrix of dimensions m × m is a linear combination of the basic positive alternating cycle matrices P_{1}, P_{2}, …, P_{m}, where P_{1} = I, the identity matrix, P_{k} (k = 2, .., m1) the matrix that has 0’s on its principal diagonal, 0’s on its secondary diagonal if m is an even number, and all positive cycles are composed of only 0’s with the exception of one positive alternating (0,1)cycle that passes through the kth element of the first row, such that P_{k}(1,k) = 1. If m is an even number, then P_{m} is the matrix that has 1’s on its secondary diagonal and 0’s elsewhere. If m is an odd number, then P_{m} is defined like P_{k} before. Figures 1 and 2 illustrate the basic positive alternating cycle matrices in the cases m=4 and m=5.
The basic positive alternating cycle matrices (m=4)
The basic positive alternating cycle matrices (m=5) Figure 2 The positive alternating cycle matrix
P of dimensions 5×5 with (a b c d e) as its first row
(Figure 3) may be written as: P = aP_{1}
+ bP_{2} + cP_{3} + dP_{4}
+ eP_{5}.
Matrix P Figure 3 Similarly, any negative alternating cycle matrix of dimensions m × m is a linear combination of the basic negative alternating cycle matrices N_{1}, N_{2}, …, N_{m}, where N_{k} (k = 1, .., m1) is the matrix that has 0’s on its secondary diagonal if m is an odd number, and all its negative cycles are composed of only 0’s with the exception of one negative alternating (0,1)cycle that passes through the kth element of the first row, such that N_{k}(1,k) = 1. If m is an even number, then N_{m} is defined like N_{k} before. If m is an odd number, then N_{m} is the matrix that has 1’s on its secondary diagonal and 0’s elsewhere. Figures 4 and 5
illustrate the basic negative alternating cycle matrices in the cases m=4
and m=5.
The basic negative alternating cycle matrices (m=4)
The basic negative alternating cycle matrices (m=5) Figure 5 Basic positive and negative alternating cycle matrices as permutation matrices The basic positive and negative alternating cycle matrices of dimensions m x m constitute a particular class of permutation matrices. The elements of this class admit a circular representation. Consider 2m points equally spaced around a circle, numbered clockwise 1, 2, …, m, m, m1, …, 2, 1, being the first m points on the right side and the other m points on the left side. The circular representation of a basic alternating cycle matrix consists of a directed graph joining points around the circle. Figure 6 displays
the circular representation of the basic positive alternating cycle matrices
P_{2}, P_{3}, P_{4} and P_{5}
in the case m=5. The representation corresponds to the cycle notation
of the respective permutations: (1 3 5 4 2) for P_{2}, (1
2 4 5 3) for P_{3}, (1 5 2 3 4) for P_{4},
and (1 4 3 2 5) for P_{5}. In the circular representation
one advances in the case of P_{2}, each time clockwise 2
points: from the right 1point to the right 3point, etc. In the case of
P_{3}, one advances each time anticlockwise 2 points: from
the right 1point to the left 2point, etc. In the case of P_{4},
one advances each time clockwise 4 points. In the case of P_{5},
one advances each time anticlockwise 4 points.
(a)
(b)
(c)
(d) Circular representation of P_{2}, P_{3}, P_{4} and P_{5} in the case m=5 Figure 6 Figure 7 displays the circular representation of the basic negative alternating cycle matrices N_{1}, N_{2}, N_{3}, N_{4} and N_{5} in the case m=5. Once again the representation corresponds to the cycle notation of the respective permutations: (2 3) (4 5) for N_{1} , (1 2) (3 4) for N_{2}, (1 3) (2 5) for N_{3}, (1 4)(3 5) for N_{4}, and (1 5)(2 4) for N_{5}. Either one starts at the 1point at the left, as is the case of N_{1}, N_{3} and N_{5}, or at the 1point at the right, as is the case of N_{2} and N_{4}, and advances clockwise.
(a)
(b)
(c)
(d)
(e) Circular representation of N_{1}, N_{2}, N_{3}, N_{4} and N_{5} in the case m=5 Figure 7 Table 1 summarizes the structure of the circular representations of the basic positive and the basic negative alternating cycle matrices, where C2 refers to advancing clockwise each time two points; A4 means advancing each time anticlockwise 4 points. L5 means starting at the 1point at the left side and advancing clockwise each time 5 points; R3 means starting at the 1point at the right side and advancing clockwise each time 3 points, etc.
Basic alternating cycle matrices and structure of corresponding circular representations (m = 5) Table 1 Let us now analyse for any m the relationship between basic positive and negative alternating cycle matrices and the structure of their circular representation. We may extrapolate that the following proposition is valid: * The circular representation of N_{k} is R(k1), if k is an even number (1 < k £ m), and Lk, if k is an odd number. Let us prove the first case: if k
is an odd number (1 < k £
m), then the circular representation
of P_{k} has as structure A(k1). As k
is odd, there exists a natural number
s such that k = 2s+1.
The sth positive cycle passes through the first row in (1, k1)
and (1,k). According to the definition of P_{k},
it has a 0 in (1, k1) and a 1 in (1,k) (Figure 8).
Figure 8 As a permutation matrix, P_{k} transforms the kth element into the 1^{st}. This leads to two possibilities for the circular representation, as Figure 9 illustrates, either there is an arrow from the kpoint on the left to the right 1point, or there is an arrow from the right kpoint to the right 1point. The first possibility would correspond to Ck, the second to A(k1).
Ck A(k1) Two possibilities Figure 9 P_{k} transforms the (k2)th element into the 2^{nd} element and/or the (k+2)th element into the 3^{rd} element (see Figure 8). In the first scenario this would correspond to clockwise advances of (k1) points, what is not compatible with Ck. In the second scenario, it would correspond to anticlockwise advances of k1 points from the (k2)point on the right to the 2point on the left, and from the (k+2)point on the right to the 3point on the right side, both in agreement with A(k1). Thus A(k1) is the only possible structure for the circular representation of P_{k}. Remains to be analysed if it really describes the whole transformation. Consider first the odd elements. On the one hand P_{k} transforms the (k+2t)th element into the (2t+1)th element (cf. Figure 8), if k+2t £ m. Thus, the arrow goes from the (k+2t)point on the right side to the (2t+1)point on the same side, advancing anticlockwise (k+2t)(2t+1), that is k1 points. On the other hand P_{k} transforms the (k2t)th element into (2t)th element, if 1 £ k2t. Therefore, the arrow goes from the (k2t)point on the right side to the 2tpoint on the left side, advancing anticlockwise ((k2t)1)+2t, that is k1 points. Consider now the even elements. We have to distinguish two different situations: 2k £ m and 2k > m (see Figure 10).
Cycle form in the cases 2k £ m and 2k > m Figure 10 In the first case 2k £ m, firstly, P_{k} transforms the (k12t)th element into the [2(k1)2t]th element, where 1 £ k12t. In other words, the arrow goes from the (k12t)point on the left to the [2(k1)2t]point on the left side, corresponding to an anticlockwise advance of [2(k1)2t]  (k12t) or k1 points, in agreement with the predicted structure A(k1). Secondly P_{k} transforms the (k+1+2t)th element into the (2k+2t)th element, where k+1+2t £ mk. This means that the arrow goes from (k+1+2t)point on the left to the (2k+2t)th on the same side, once again corresponding to an anticlockwise advance of k1 points. Thirdly P_{k} transforms the (mk+3+2t)th element into the (m12t)th element, if k > 3+2t and if m is an even number. This means the arrow goes from the (mk+3+2t)point on the left side to the (m12t)point on the right side, corresponding to an anticlockwise rotation of (k32t) + 1+ (1+2t), that is, of k1 points. And finally P_{k} transforms the (mk+2+2t)th element into the (m2t)th element, if k > 2+2t and if m is an odd number. In other words, the arrow goes from the (mk+2+2t)point on the left side to the (m2t)point on the right side, corresponding to an anticlockwise rotation of (k22t) + 1+ (2t), that is, of k1 points. In the second case 2k > m, a similar reasoning leads to the same result. We may conclude that, if k is an odd number (1 < k £ m), then the circular representation of P_{k} has the structure A(k1). The other three parts of the theorem may be proven analogously. Theorem 1 * The circular representation of N_{k}
is R(k1), if k is an even number (1 < k
£
m), and Lk, if k is an odd number.
Let us now calculate the multiplication tables of the basic positive and negative alternating cycle matrices of dimensions m × m. 1) Positive times positive (multiplication table 1) Firstly we shall consider the products of basic positive alternating cycle matrices of dimensions m × m: P_{u} × P_{v} = ? Depending on u and v being even or odd numbers, we have to distinguish four cases. Case 1: u and v are even numbers. Otherwise, if u+v > m, we have [C(u+v)] = [A(2m(u+v))] = P_{(2muv+1)}. Otherwise, if u < v, we have P_{u} × P_{v} = [Cu + A(v1)] = [A(v1u)] = [A(vu1)] = P_{(vu)}. Otherwise, if u < v, we have P_{u} × P_{v} = [A(u1) + Cv] = [C(vu+1)] = P_{(vu+1)}. Otherwise, if u+v1 >
m, we have P_{u} × P_{v}
= [A(u+v2)] = [C(2m(u+v2))]
= P_{(2muv+2)}.
Secondly we shall consider the products of basic positive alternating cycle matrices of dimensions m × m times basic negative alternating cycle matrices of the same dimensions: P_{u} × N_{v} = ? Depending on u and v being even or odd numbers, we have to distinguish four cases. Case 1: u and v are even numbers. Otherwise, if u > v, we have P_{u} × N_{v} = [Cu + R(v1)] = [R(v(u+1))] = N_{(vu)}. Otherwise, if u+v > m, we have P_{u} × N_{v} = [R(2muv)] = N_{(2muv+1)}. Otherwise, if u+v1 > m, we have P_{u }× N_{v} = [R(u+v2)] = [L(2muv+2)] = N_{(2muv+2)}. Otherwise, if u > v,
we have P_{u} × N_{v} = [A(u1)
+ L(v)] = [L(v(u1)]= N_{(vu+1)}.
Thirdly we shall consider the products of basic negative alternating cycle matrices of dimensions m × m times basic positive alternating cycle matrices of the same dimensions: N_{u} × P_{v} = ? We have to distinguish four cases. Case 1: u and v are even numbers. Otherwise, if u+v > m, we have N_{u} × P_{v} = [R(u+v1)] = [L(2muv+1)] = N_{(2muv+1)}. Otherwise, if v < u, we have N_{u} × P_{v} = [R(uv)] = N_{(uv+1)}. Otherwise, if u > v, we have N_{u} × P_{v} = [Lu + Cv] = [L(uv)] = N_{(uv)}. Otherwise, if u+v1 >
m, we have N_{u} × P_{v} = [Lu
+ A(v1)] = [R(2muv+1)] = N_{(2muv+2)}.
Fourthly we have to consider the products of basic negative alternating cycle matrices of dimensions m × m: N_{u} × N_{v} = ? Once again we have to distinguish four cases. Case 1: u and v are even numbers. Otherwise, if u > v, we have N_{u} × N_{v} = [C(vu)] = P_{(vu)}. Otherwise, if u+v > m, we have N_{u} × N_{v} = [A(u+v1)] = [C(2muv+1)] = P_{(2muv+1)}. Otherwise, if u+v1 > m, we have N_{u} × N_{v} = [A(2muv+1)] = P_{(2muv+2)}. Otherwise, if u £
v, we have N_{u} × N_{v} = [A(vu)]
= P_{(vu+1)}.
Comparing case by case the results of the multiplication of P_{u} × P_{v} (multiplication table 1) with those of the multiplication of N_{u} × P_{v} (multiplication table 3), we see that P_{u} × P_{v} = P_{s} if and only if N_{u} × P_{v} = N_{s}. In other words, the respective multiplication
tables have the same associated matrix of indices. Figure
11 illustrates, the cases m=5 and m=6.
m=5
m=6 Multiplication tables and associated matrix Figure 11 Moreover and surprisingly, the associated matrix itself is also a negative alternating cycle matrix. We found the following theorem. Theorem 2 Comparing case by case the results of the multiplication of P_{u} × N_{v} (multiplication table 2) with those of the multiplication of N_{u}_{ }× N_{v} (multiplication table 4), we see that P_{u} × N_{v} = N_{s} if and only if N_{u} × N_{v} = P_{s}. In other words, the respective multiplication
tables have the same associated matrix of indices. Figure
12 illustrates, the cases m=5 and m=6.
m=5
m=6 Multiplication tables and associated matrix Figure 12 The structure of the associated matrix is that of a positive alternating cycle matrix. Thus, we arrive at the following theorem. Theorem 3 As positive alternating cycle matrices are linear combinations of basic positive alternating cycle matrices and as negative alternating cycle matrices are linear combinations of basic negative alternating cycle matrices, the multiplication tables imply the following theorem: Theorem 4
Figure 13 From multiplication table 1, it follows immediately that P_{u} × P_{v} = P_{v} × P_{u} for all u and v. In other words, the multiplication of basic positive alternating cycle matrices is commutative. Supposing the matrix elements of positive alternating cycle matrices belong to a field, we find that the following theorem is true. Theorem 5 In agreement with the circular representation of basic positive alternating cycles (Theorem 1) and the subsequent multiplication table 1, we have for basic positive alternating cycle matrices several other properties, like P_{2}P_{3} = P_{4}P_{5} = P_{6}P_{7} = … = I, P_{1}P_{2}P_{3}…..P_{(2n+1)} = I, (P_{s})^{m} = I. From multiplication table 4, it follows that the matrices N_{u} × N_{v}_{ }and N_{v} × N_{u}_{ }are symmetrical in the sense that a reflection in the principal diagonal of the first matrix transforms it into the second matrix. In the other words, the second matrix is the transposed matrix of the first one: N_{u} × N_{v} = [N_{v} × N_{u}]’ Supposing the matrix elements of negative alternating cycle matrices belong to a field, we find that the following theorem is true. Theorem 6
References
on cycle matrices:
Gerdes, Paulus (2002a), From Likidesigns to cycle matrices: The discovery of attractive new symmetries, Visual Mathematics, Vol. 4, No. 1, (http://members.tripod.com/vismath7/gerd/) Gerdes, Paulus (2002b), Helix matrices, Visual Mathematics, Vol. 4, No. 2, June 2002 (http://members.tripod.com/vismath8/gerdhel/hel.htm) Gerdes, Paulus (2002c), Cylinder matrices, Visual Mathematics, Vol. 4, No. 2, June 2002 (http://members.tripod.com/vismath8/gerdcyl/cyl1.htm) Gerdes, Paulus (2004), Aventuras no Mundo das Matrizes [Adventures in the World of Matrices], book manuscript Gerdes, Paulus (2005), Mathematical research inspired by African cultural practices: The example of mirror curves, Lundadesigns and related concepts, in: Giandomenico Sica (Ed.), What Mathematics from Africa?, Polimetrica, Milano, 2005, 2947. Gerdes, Paulus (2006), Symmetries of alternating cycle matrices, paper submitted to Visual Mathematics.
