Definition: A matrix $M$ of order $n$ over a field is a $\operatorname{MDS}$ matrix if and only if every sub-matrix of $M$ is non-singular.

My question: How to proof the following statement.

If $A$ be a $p^d \times p^d$ orthogonal $\operatorname{MDS}$ matrix over $\operatorname{GF}(p^q)$ then $A$ is not a circulant matrix.

Previous work: In the case $p=2$, the proof is done by the lemma 5 in this paper as follows.

Consider $A$ be a circulant matrix in the following form $A=circ(a_o,a_1,\cdots, a_{2^d-1})$. It can be proved that determinant of $A$ is $$ \det(A)=\sum_{i=0}^{2^d-1}a_i^{2^d}=(\sum_{i=0}^{2^d-1}a_i)^{2^d} $$ since $A$ can be presented by the form $A=\sum_{i=0}^{2^d-1}a_iP^i$ where $P$ is a permutation matrix. Moreover, due to $A$ is a orthogonal matrix, if $R_i$, $0\leq i \leq 2^d-1$, be the $i$th row of the matrix $A$ then $R_i\cdot R_j=0$ for $i\neq j$.

Suppose that $j=\{2k+1, k=0 \cdots 2^{d-2}-1\}$, then from $R_0\cdot R_j=0$, we get $$ (a_0+a_2+\cdots + a_{2^d-2})\,(a_1+a_3+\cdots + a_{2^d-1})=0 \tag{1} $$ At least, one of the terms of $(1)$ should be zero. Let $(a_0+a_2+\cdots + a_{2^d-2})=0$. Consider circulant sub-matrix $B=circ(a_0,a_2,\cdots , a_{2^d-2})$ of $A$ then we can conclude that $$ \det(B)=\sum_{i=0}^{2^{d-1}-1}a_{2i}^{2^{d-1}}=(\sum_{i=0}^{2^{d-1}-1}a_{2i})^{2^{d-1}}=0 $$ that is contradiction to the assumptions that $A$ is a $\operatorname{MDS}$ matrix.$\qquad \blacksquare$

My problem to extend the mentioned proof for the case $p>2$ is that i can not find a circulant sub-matrix like the case $2^d\times 2^d$. May be my question was not true for the case $p>2$.

If it is proved in some paper please reference it. Thanks for any suggestions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.