Let $A=\{a\_{ij}\}$ be a [normal](http://en.wikipedia.org/wiki/Normal_matrix) 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](http://en.wikipedia.org/wiki/Circulant_matrix) matrix?


Note: There is a partial classification of non-negative normal matrices posted [here](http://www.math.ohiou.edu/~jain/073.pdf), 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](https://math.stackexchange.com/questions/1092185/is-a-normal-matrix-satisfying-ata-circulant)



Is a normal matrix satisfying $A^TA=...$ circulant?
**NO**.


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$.


