Transpositions matrix

Transpositions matrix $Tr=(Tr_{i,j})_{\begin{smallmatrix}i={1,n}\\j={1,n}\end{smallmatrix}}$ ($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)={\begin{pmatrix}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}\\\end{pmatrix}}$

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.

Fours of elements in Tr matrix

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 ($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},...r_{n}]^{T},r_{2},...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},...r_{n}]^{T},r_{2},...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.

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}}$ is obtained as:

$Trs(X)=H\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 $I_{n}$ is n-dimensional Identity matrix. [5] gives as examples code of a Matlab functions that creates $Tr$ and $Trs$ matrices for a given 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

1. Harville, D. A. (1997). Matrix Algebra from Statistician’s Perspective. Softcover.
2. Horn, Roger A.; Johnson, Charles R. (2013), Matrix analysis (2nd ed.), Cambridge University Press, ISBN 978-0-521-54823-6
3. Mirsky, Leonid (1990), An Introduction to Linear Algebra, Courier Dover Publications, ISBN 978-0-486-66434-7
4. 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.
5. 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.