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{array}{c}i=1,n\end{array}}$ as follows: $T{r}_{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=\left(\begin{array}{c}{x}_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8\end{array}\right)$ $$Tr(X)=\left[\begin{array}{cccccccc}{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{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 $T{r}_{p,q}$ and $T{r}_{u,q}$ are two arbitrary selected elements from the same column q of $Tr$ matrix, then, $Tr$ matrix consists one fours of elements $(T{r}_{p,q},T{r}_{u,q},T{r}_{p,v},T{r}_{u,v})$, for which are satisfied the equations $T{r}_{p,q}=T{r}_{u,v}$ and $T{r}_{u,q}=T{r}_{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 and columns ($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})$, $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={\left(\begin{array}{c}{x}_1,x_2,x_3,x_4\end{array}\right)}^T$ is obtained as:

$$Trs(X)=H(R)\circ Tr(X)=\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& -1& 1& -1\\ 1& -1& -1& 1\\ 1& 1& -1& -1\end{array}\right)\circ \left(\begin{array}{cccc}{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{array}\right)=\left(\begin{array}{cccc}{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{array}\right)$$ 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={\Vert X\Vert }^2\left[\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right]$$

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

References

1. Template:Cite book
2. Template:Citation
3. Template:Citation
4. Template:Cite journal
5. Template:Cite book

External links

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