Transpositions matrix
Transpositions matrix (Tr matrix) is square n \times n matrix, n=2^{m} , m \in N , which elements are obtained from the elements of given n-dimensional vector X=(x_i)_{\begin{smallmatrix} i={1,n} \end{smallmatrix}} as follows: Tr_{i,j} =…
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Transpositions matrix (Tr matrix) is square n \times n matrix, n=2^{m} , m \in N , which elements are obtained from the elements of given n-dimensional vector X=(x_i)_{\begin{smallmatrix} i={1,n} \end{smallmatrix}} as follows: Tr_{i,j} = x_{(i-1) \oplus (j-1)+1} , where \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 The figure below shows Transpositions matrix Tr(X) of order 8, created from arbitrary vector X=\begin{pmatrix}x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8 \\\end{pmatrix} 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] Every two rows Tr matrix consists n/2 fours of elements with the same values of the diagonal elements.
In example if Tr_{p,q} and Tr_{u,q} are two arbitrary selected elements from the same column q of Tr matrix, then, Tr matrix consists one fours of elements ( Tr_{p,q}, Tr_{u,q}, Tr_{p,v}, Tr_{u,v}) , for which are satisfied the equations Tr_{p,q}=Tr_{u,v} and Tr_{u,q} = Tr_{p,v} . This property, named “Tr-property” is specific to Tr matrices.
The figure on the right shows some fours of elements in Tr matrix. The property of fours of Tr matrices gives the possibility to create matrix with mutually orthogonal rows and columns ( Trs matrix ) by changing the sign to an odd number of elements in every one of fours ( Tr_{p,q}, Tr_{u,q}, Tr_{p,v}, Tr_{u,v}) , p,q,u,v \in [1,n] . In [5] is offered algorithm for creating Trs matrix using Hadamard product, (denoted by \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, \dots, r_n]^T , r_2, \dots, r_n \in [2,n] , for which the rows of the resulting Trs matrix are mutually orthogonal.
Trs(X) = Tr(X)\circ H(R) Trs.{Trs}^T=\parallel X\parallel^2.I_n where: " \circ " denotes operation Hadamard product I_n is n-dimensional Identity matrix. H(R) is n-dimensional Hadamard matrix, which rows are interchanged against the Sylvester-Hadamard[4] matrix in given order 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.
X is the vector from which the elements of Tr matrix are derived. Orderings R of Hadamard matrix’s rows were obtained experimentally for Trs matrices of sizes 2, 4 and 8.
The ordering R of Hadamard matrix’s rows (against the Sylvester-Hadamard matrix) does not depend on the vector X . Has been proven[5] that, if X is unit vector (i.e. \parallel X\parallel=1 ), then Trs matrix (obtained as it was described above) is matrix of reflection. Transpositions matrix with mutually orthogonal rows ( Trs matrix) of order 4 for vector X = \begin{pmatrix} x_1, x_2, x_3, x_4 \end{pmatrix}^T is obtained as: 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 Tr(X) is Tr matrix, obtained from vector X , and " \circ " denotes operation Hadamard product and H(R) is Hadamard matrix, which rows are interchanged in given order R for which the rows of the resulting Trs matrix are mutually orthogonal.
As can be seen from the figure above, the first row of the resulting Trs matrix contains the elements of the vector X without transpositions and sign change. Taking into consideration that the rows of the Trs matrix are mutually orthogonal, we get Trs(X).X = \left\| X \right\|^2 \begin{bmatrix}1 \\ 0 \\ 0 \\ 0\end{bmatrix} which means that the Trs matrix rotates the vector X , from which it is derived, in the direction of the coordinate axis x_1 In [5] are given as examples code of a Matlab functions that creates Tr and Trs matrices for vector X of size n = 2, 4, or, 8.
Stay open question is it possible to create Trs matrices of size, greater than 8.
See also
Symmetric matrix Persymmetric matrix Orthogonal matrix
External links
http://article.sapub.org/10.5923.j.ajcam.20190904.03.html
Text derived from https://en.wikipedia.org/w/index.php?oldid=1368367188 under CC BY-SA 4.0; modifications have been made.