# 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

• @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