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} = 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

Example

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]$

Properties

$Tr$ matrix is symmetric matrix.
$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 $Tr$ matrix consists all n elements of given vector $X$ without repetition.
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.

File:Trs Matrix Fours.png

The figure on the right shows some fours of elements in $Tr$ matrix.

Transpositions matrix with mutually orthogonal rows (Trs 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. 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$ . 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.

Example of obtaining Trs matrix

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.

References

{{cite book|last=Harville|first=D. A.|title=Matrix Algebra from Statistician’s Perspective|year=1997|publisher=Softcover}}
{{citation|last=Horn|first= Roger A.|last2= Johnson|first2= Charles R.|title= Matrix analysis|edition=2nd| publisher=Cambridge University Press|year= 2013|isbn= 978-0-521-54823-6}}
{{Citation |last1=Mirsky |first1=Leonid |author-link=Leon Mirsky |title=An Introduction to Linear Algebra |url=https://books.google.com/books?id=ULMmheb26ZcC&dq=linear+algebra+determinant&pg=PA1 |publisher=Courier Dover Publications |isbn=978-0-486-66434-7 |year=1990 }}
{{cite journal|first1=L. D. | last1=Baumert | first2=Marshall | last2=Hall

|title=Hadamard matrices of the Williamson type

|doi=10.1090/S0025-5718-1965-0179093-2 |mr=0179093| doi-access=free }}

{{cite book|last=Zhelezov|first=O. I.|title=Determination of a Special Case of Symmetric Matrices and Their Applications|year=2021|publisher=Current Topics on Mathematics and Computer Science Vol. 6, 29–45|isbn= 978-93-91473-89-1}}

External links

http://article.sapub.org/10.5923.j.ajcam.20190904.03.html

Category:Matrices (mathematics)