Transpositions matrix (Tr matrix) is square n × n {\displaystyle n\times n} matrix, n = 2 m {\displaystyle n=2^{m}} , m ∈ N {\displaystyle m\in N} , which elements are obtained from the elements of given n-dimensional vector X = ( x i ) i = 1 , n {\displaystyle X=(x_{i})_{\begin{smallmatrix}i={1,n}\end{smallmatrix}}} as follows: T r i , j = x ( i − 1 ) ⊕ ( j − 1 ) + 1 {\displaystyle Tr_{i,j}=x_{(i-1)\oplus (j-1)+1}} , where ⊕ {\displaystyle \oplus } denotes operation "bitwise Exclusive or" (XOR). The rows and columns of Transpositions matrix consists permutation of elements of vector X, as there are n/2 transpositions between every two rows or columns of the matrix
Example
The figure below shows Transpositions matrix T r ( X ) {\displaystyle Tr(X)} of order 8, created from arbitrary vector X = ( x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 , x 8 ) {\displaystyle X={\begin{pmatrix}x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8}\\\end{pmatrix}}} T r ( X ) = [ x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 2 x 1 x 4 x 3 x 6 x 5 x 8 x 7 x 3 x 4 x 1 x 2 x 7 x 8 x 5 x 6 x 4 x 3 x 2 x 1 x 8 x 7 x 6 x 5 x 5 x 6 x 7 x 8 x 1 x 2 x 3 x 4 x 6 x 5 x 8 x 7 x 2 x 1 x 4 x 3 x 7 x 8 x 5 x 6 x 3 x 4 x 1 x 2 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 ] {\displaystyle Tr(X)=\left[{\begin{array}{cccc|ccccc}x_{1}&x_{2}&x_{3}&x_{4}&x_{5}&x_{6}&x_{7}&x_{8}\\x_{2}&x_{1}&x_{4}&x_{3}&x_{6}&x_{5}&x_{8}&x_{7}\\x_{3}&x_{4}&x_{1}&x_{2}&x_{7}&x_{8}&x_{5}&x_{6}\\x_{4}&x_{3}&x_{2}&x_{1}&x_{8}&x_{7}&x_{6}&x_{5}\\\hline x_{5}&x_{6}&x_{7}&x_{8}&x_{1}&x_{2}&x_{3}&x_{4}\\x_{6}&x_{5}&x_{8}&x_{7}&x_{2}&x_{1}&x_{4}&x_{3}\\x_{7}&x_{8}&x_{5}&x_{6}&x_{3}&x_{4}&x_{1}&x_{2}\\x_{8}&x_{7}&x_{6}&x_{5}&x_{4}&x_{3}&x_{2}&x_{1}\end{array}}\right]}
Properties
- T r {\displaystyle Tr} matrix is symmetric matrix.
- T r {\displaystyle Tr} matrix is persymmetric matrix, i.e. it is symmetric with respect to the northeast-to-southwest diagonal too.
- Every one row and column of T r {\displaystyle Tr} matrix consists all n elements of given vector X {\displaystyle X} without repetition.
- Every two rows T r {\displaystyle Tr} matrix consists n / 2 {\displaystyle n/2} fours of elements with the same values of the diagonal elements. In example if T r p , q {\displaystyle Tr_{p,q}} and T r u , q {\displaystyle Tr_{u,q}} are two arbitrary selected elements from the same column q of T r {\displaystyle Tr} matrix, then, T r {\displaystyle Tr} matrix consists one fours of elements ( T r p , q , T r u , q , T r p , v , T r u , v ) {\displaystyle (Tr_{p,q},Tr_{u,q},Tr_{p,v},Tr_{u,v})} , for which are satisfied the equations T r p , q = T r u , v {\displaystyle Tr_{p,q}=Tr_{u,v}} and T r u , q = T r p , v {\displaystyle Tr_{u,q}=Tr_{p,v}} . This property, named “Tr-property” is specific to T r {\displaystyle Tr} matrices.
The figure on the right shows some fours of elements in T r {\displaystyle Tr} matrix.
Transpositions matrix with mutually orthogonal rows (Trs matrix)
The property of fours of T r {\displaystyle Tr} matrices gives the possibility to create matrix with mutually orthogonal rows and columns ( T r s {\displaystyle Trs} matrix ) by changing the sign to an odd number of elements in every one of fours ( T r p , q , T r u , q , T r p , v , T r u , v ) {\displaystyle (Tr_{p,q},Tr_{u,q},Tr_{p,v},Tr_{u,v})} , p , q , u , v ∈ [ 1 , n ] {\displaystyle p,q,u,v\in [1,n]} . In [5] is offered algorithm for creating T r s {\displaystyle Trs} matrix using Hadamard product, (denoted by ∘ {\displaystyle \circ } ) of Tr matrix and n-dimensional Hadamard matrix whose rows (except the first one) are rearranged relative to the rows of Sylvester-Hadamard matrix in order R = [ 1 , r 2 , … , r n ] T , r 2 , … , r n ∈ [ 2 , n ] {\displaystyle R=[1,r_{2},\dots ,r_{n}]^{T},r_{2},\dots ,r_{n}\in [2,n]} , for which the rows of the resulting Trs matrix are mutually orthogonal.
T r s ( X ) = T r ( X ) ∘ H ( R ) {\displaystyle Trs(X)=Tr(X)\circ H(R)} T r s . T r s T =∥ X ∥ 2 . I n {\displaystyle Trs.{Trs}^{T}=\parallel X\parallel ^{2}.I_{n}}
where:
- " ∘ {\displaystyle \circ } " denotes operation Hadamard product
- I n {\displaystyle I_{n}} is n-dimensional Identity matrix.
- H ( R ) {\displaystyle H(R)} is n-dimensional Hadamard matrix, which rows are interchanged against the Sylvester-Hadamard[4] matrix in given order R = [ 1 , r 2 , … , r n ] T , r 2 , … , r n ∈ [ 2 , n ] {\displaystyle R=[1,r_{2},\dots ,r_{n}]^{T},r_{2},\dots ,r_{n}\in [2,n]} for which the rows of the resulting T r s {\displaystyle Trs} matrix are mutually orthogonal.
- X {\displaystyle X} is the vector from which the elements of T r {\displaystyle Tr} matrix are derived.
Orderings R of Hadamard matrix’s rows were obtained experimentally for T r s {\displaystyle Trs} matrices of sizes 2, 4 and 8. It is important to note, that the ordering R of Hadamard matrix’s rows (against the Sylvester-Hadamard matrix) does not depend on the vector X {\displaystyle X} . Has been proven[5] that, if X {\displaystyle X} is unit vector (i.e. ∥ X ∥= 1 {\displaystyle \parallel X\parallel =1} ), then T r s {\displaystyle Trs} matrix (obtained as it was described above) is matrix of reflection.
Example of obtaining Trs matrix
Transpositions matrix with mutually orthogonal rows ( T r s {\displaystyle Trs} matrix) of order 4 for vector X = ( x 1 , x 2 , x 3 , x 4 ) T {\displaystyle X={\begin{pmatrix}x_{1},x_{2},x_{3},x_{4}\end{pmatrix}}^{T}} is obtained as:
T r s ( X ) = H ( R ) ∘ T r ( X ) = ( 1 1 1 1 1 − 1 1 − 1 1 − 1 − 1 1 1 1 − 1 − 1 ) ∘ ( x 1 x 2 x 3 x 4 x 2 x 1 x 4 x 3 x 3 x 4 x 1 x 2 x 4 x 3 x 2 x 1 ) = ( x 1 x 2 x 3 x 4 x 2 − x 1 x 4 − x 3 x 3 − x 4 − x 1 x 2 x 4 x 3 − x 2 − x 1 ) {\displaystyle Trs(X)=H(R)\circ Tr(X)={\begin{pmatrix}1&1&1&1\\1&-1&1&-1\\1&-1&-1&1\\1&1&-1&-1\\\end{pmatrix}}\circ {\begin{pmatrix}x_{1}&x_{2}&x_{3}&x_{4}\\x_{2}&x_{1}&x_{4}&x_{3}\\x_{3}&x_{4}&x_{1}&x_{2}\\x_{4}&x_{3}&x_{2}&x_{1}\\\end{pmatrix}}={\begin{pmatrix}x_{1}&x_{2}&x_{3}&x_{4}\\x_{2}&-x_{1}&x_{4}&-x_{3}\\x_{3}&-x_{4}&-x_{1}&x_{2}\\x_{4}&x_{3}&-x_{2}&-x_{1}\\\end{pmatrix}}} where T r ( X ) {\displaystyle Tr(X)} is T r {\displaystyle Tr} matrix, obtained from vector X {\displaystyle X} , and " ∘ {\displaystyle \circ } " denotes operation Hadamard product and H ( R ) {\displaystyle H(R)} is Hadamard matrix, which rows are interchanged in given order R {\displaystyle R} for which the rows of the resulting T r s {\displaystyle Trs} matrix are mutually orthogonal. As can be seen from the figure above, the first row of the resulting T r s {\displaystyle Trs} matrix contains the elements of the vector X {\displaystyle X} without transpositions and sign change. Taking into consideration that the rows of the T r s {\displaystyle Trs} matrix are mutually orthogonal, we get T r s ( X ) . X = ‖ X ‖ 2 [ 1 0 0 0 ] {\displaystyle Trs(X).X=\left\|X\right\|^{2}{\begin{bmatrix}1\\0\\0\\0\end{bmatrix}}}
which means that the T r s {\displaystyle Trs} matrix rotates the vector X {\displaystyle X} , from which it is derived, in the direction of the coordinate axis x 1 {\displaystyle x_{1}}
In [5] are given as examples code of a Matlab functions that creates T r {\displaystyle Tr} and T r s {\displaystyle Trs} matrices for vector X {\displaystyle X} of size n = 2, 4, or, 8. Stay open question is it possible to create T r s {\displaystyle Trs} matrices of size, greater than 8.
See also
- Mathematics portal
- Harville, D. A. (1997). Matrix Algebra from Statistician’s Perspective. Softcover.
- Horn, Roger A.; Johnson, Charles R. (2013), Matrix analysis (2nd ed.), Cambridge University Press, ISBN 978-0-521-54823-6
- Mirsky, Leonid (1990), An Introduction to Linear Algebra, Courier Dover Publications, ISBN 978-0-486-66434-7
- Baumert, L. D.; Hall, Marshall (1965). "Hadamard matrices of the Williamson type". Math. Comp. 19 (91): 442–447. doi:10.1090/S0025-5718-1965-0179093-2. MR 0179093.
- Zhelezov, O. I. (2021). Determination of a Special Case of Symmetric Matrices and Their Applications. Current Topics on Mathematics and Computer Science Vol. 6, 29–45. ISBN 978-93-91473-89-1.