Let $A=\{a_{ij}\}$ be a normal matrix such that $a_{ij}\geq 0$ with equality iff $i=j$. Suppose that $$ A^TA=\begin{pmatrix} a & b & \cdots & b\\ b & a & \ddots & \vdots\\ \vdots & \ddots & a & b\\ b & \cdots & b & a\\ \end{pmatrix},\ where\ b>0. $$ Does it follow that $A$ is a circulant matrix?

Note: There is a partial classification of non-negative normal matrices posted here, which seems like it can be used to attack this problem.

There is a geometric interpretation as well: both the set of rows and the set of columns of $A$ form equidistant sets of vectors on a sphere, and basic geometry appears to severely restrict the possibilities.

Reposted from math.SE



Let $A$ satisfy the assumptions. If $P$ is a permutation matrix, then $B:=PA$ satisfies the assumptions too: on the one hand, we have $B^TB=A^TP^TPA=A^TA$. On the other hand (remark that the matrix in the question is permutation-invariant) $$BB^T=PAA^TP^T=PA^TAP^T=A^TA=B^TB.$$

If the claim is true, we find that $B=PA$ is circulant for every permutation matrix $P$. We deduce that $a_{ij}$ not only depends upon $j-i$ (modulo $n$), but also depends only upon $j-\sigma(i)$, for every $\sigma\in{\frak S}_n$. We conclude that $a_{ij}$ is constant.

Therefore every matrix $A$ satisfying the assumptions, such that $a_{ij}$ is not constant, provides a counter-example of the form $PA$ for some (many) permutation matrices $P$.

  • $\begingroup$ Very nice. I observed the cyclic invariance but didn't think to extend to arbitrary permutation invariance. $\endgroup$ – pre-kidney Jan 13 '15 at 7:31
  • $\begingroup$ I am interested in whether the same question holds, but now up to row/column permutation. I have posted the new version here: mathoverflow.net/questions/193803/… $\endgroup$ – pre-kidney Jan 13 '15 at 7:52

No consider for example $$A=\begin{pmatrix}0 & 1 & 1+\sqrt{2} & \sqrt{2}\\1+\sqrt{2} & 0 & \sqrt{2} & 1\\1 & \sqrt{2} & 0 &1+\sqrt{2}\\\sqrt{2} & 1+\sqrt{2} & 1 & 0 \end{pmatrix}.$$


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.