1
$\begingroup$

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.

$\endgroup$

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.