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?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ Where does this problem come from? What is the motivation? $\endgroup$– Rodrigo de AzevedoCommented Apr 18, 2018 at 16:17
-
2$\begingroup$ 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. $\endgroup$– Student88Commented Apr 22, 2018 at 9:54
-
$\begingroup$ Why must $B$ be positive rather than nonnegative? Do you only care about the diagonal of $A^3$? $\endgroup$– Rodrigo de AzevedoCommented Apr 22, 2018 at 10:05
-
$\begingroup$ 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) $\endgroup$– Student88Commented Apr 23, 2018 at 14:26
-
$\begingroup$ That means there are only $n$ constraints, rather than $n^2$. I believe you should edit your question. $\endgroup$– Rodrigo de AzevedoCommented Apr 23, 2018 at 14:32
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
3
A is a matrix with the same eigenvectors as B and with eigenvalues that are the cube roots of B's eigenvalues
-
3$\begingroup$ That's correct, but not helpful. The difficulty is hidden in the word "binary". $\endgroup$ Commented Apr 18, 2018 at 8:37
-
$\begingroup$ 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. $\endgroup$– user83457Commented Apr 18, 2018 at 14:17
-
1$\begingroup$ @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. $\endgroup$ Commented Apr 18, 2018 at 15:25