# Finding an adjacency matrix whose cube's diagonal is equal to a given vector

How can I find all binary matrices $A$ such that $A^3$ is a non-negative, integer square matrix and

$$\mbox{diag}\left(A^3\right)=b$$

for some given vector $b$? Is there a way to characterize all the solutions?

• Where does this problem come from? What is the motivation? – Rodrigo de Azevedo Apr 18 '18 at 16:17
• Hi Rodrigo, This problem actually stems from its graph interpretation as suggested below. I'm trying to characterize all the graphs (with a given number of vertices) that share the same triangle-distribution over the edges, i.e. that share the same diagonal of A^3 where A is the adjacency matrix. – MathGirl88 Apr 22 '18 at 9:54
• Why must $B$ be positive rather than nonnegative? Do you only care about the diagonal of $A^3$? – Rodrigo de Azevedo Apr 22 '18 at 10:05
• Yes, you are right, $B$ can be nonnegative. And Yes, only the diagonal of $A^3$ (which stands for the number of triangles that each vertex participates in) – MathGirl88 Apr 23 '18 at 14:26
• That means there are only $n$ constraints, rather than $n^2$. I believe you should edit your question. – Rodrigo de Azevedo Apr 23 '18 at 14:32

## 1 Answer

A is a matrix with the same eigenvectors as B and with eigenvalues that are the cube roots of B's eigenvalues

• That's correct, but not helpful. The difficulty is hidden in the word "binary". – Jan-Christoph Schlage-Puchta Apr 18 '18 at 8:37
• I wonder if the responders point isn't that you may be able to generate all cube roots reasonably efficiently and then just look through them. Possibly there is even only one reasonable choice for the eigenvalues, as e.g. you need the positive root of the largest. – user83457 Apr 18 '18 at 14:17
• @michael I doubt so. First of all, even if $B$ is diagonal with distinct eigenvalues, there are $3$ cube roots for each eigenvalue and hence $3^n$ matrix cube roots. And, moreover, you can make similar considerations for the problem "does this matrix have a square root with nonnegative entries?", and yet this is a difficult problem: as far as I know, finding a complete characterization is still an open issue. – Federico Poloni Apr 18 '18 at 15:25