2
$\begingroup$

I am currently looking at the following expression $(I - X)^{-\top} \circ X = 0$, where $\circ$ is the Hadamard product, $\top$ is the transpose, $I$ is the identity, and $X$ is non-negative and diagonal zero.

My question is for what type of matrices $X$ the above is true?

For example, if $X$ is an upper/lower triangular matrix the equation holds. But, I wonder if there are other types of matrices that fulfill such an equation. I have the intuition that $X$ being upper/triangular matrix is a necessary condition, but could not prove it.

$\endgroup$
8
  • 6
    $\begingroup$ what does the superscript $-\top$ mean? $\endgroup$ Oct 20, 2021 at 8:40
  • 3
    $\begingroup$ @CarloBeenakker I assume it's the inverse transpose. (So there is an implicit assumption that I-X is invertible, I guess.) But I don't see how this can be true for arbitrary upper triangular matrices: it's even false for diagonal matrices, as far as I can see. Perhaps the OP meant strictly upper/lower triangular. $\endgroup$ Oct 20, 2021 at 8:47
  • $\begingroup$ I’d say “triangular up to permutations”: If it is true for a matrix $X$, it is also true for $PXP^{-1}$ for any permutation matrix $P$ isn’t it? $\endgroup$ Oct 20, 2021 at 8:58
  • $\begingroup$ Is there any motivation? This sounds highly coordinate-sensitive. $\endgroup$
    – YCor
    Oct 20, 2021 at 9:58
  • $\begingroup$ @CarloBeenakker $\top$ means transpose in this case. $\endgroup$
    – Bee
    Oct 20, 2021 at 14:24

2 Answers 2

1
$\begingroup$

$\textbf{Case 1.}$ Assume that $\rho(X)<1$. $X$ is the weight matrix of a graph $\Gamma$.

Then there is a norm s.t. $||X^T||<1$.

Thus $(I-X^T)^{-1}\circ X=(I+X^T+{X^T}^2+\cdots)\circ X=I\circ X+X^T\circ X+{X^T}^2\circ X+\cdots=0$. Since the considered matrices are $\geq 0$, $0=X^T\circ X={X^T}^2\circ X=\cdots$.

$(X^T\circ X)_{i,j}=x_{j,i}x_{i,j}=0$ and $\Gamma$ has no circuit of length $\leq 2$.

For every $i$, $({X^T}^2\circ X)_{i,j}=\sum_k x_{k,i}x_{j,k}x_{i,j}=0$ (*) and $\sum_{k,i}x_{j,k}x_{k,i}x_{i,j}=0$.

Thus $\Gamma$ has no circuit of length $3$ and so on...

Finally, there is no circuit at all, $\Gamma$ is acyclic and $X^n=0$.

$\textbf{Remark.}$ (*) can be rewritten: for every $(i,j,k)$, $x_{j,k}x_{k,i}x_{i,j}=0$ -and similar relations of length $4,5,\cdots$-. To find the solutions reduces to find the entries of $X$ that necessarily are $0$ -the other ones being free-. We find exactly $n!$ such patterns and, of course, we may choose (despite the hypothesis $\rho(X) <1$) any values for the free entries of $X$.

$\textbf{Case 2.}$ It remains the case $\rho(X)\geq 1$, that is equivalent to $X$ admits an eigenvalue $\geq 1$. Let $E=\{X;x_{i,i}=0,x_{i,j}\geq 0,1\notin spectrum(X)\}$. We shew that, when $X$ goes through an open subset of $E$, the algebraic equations $(I-X^T)^{-1}\circ X=0$ implies the algebraic equations $trace(X^i)=0$. I think that we can extend the implication when $X$ goes through whole $E$. Yet, to work on the real algebraic sets is more difficult than to work on the complex ones...

$\bullet$ Unfortunately, $E$ is not a connected set.

$\endgroup$
1
  • $\begingroup$ Thanks! I also figured case 1! I did not quite understand case 2 though. Is your conclusion that the statement "$(I - X)^{-\top} \circ X = 0$ if and only if X is the weight matrix of a DAG" is false? I tried Mathematica to find a numerical counter-example and it didn't find any, which makes me want to believe the iff statement is true, but it only runs for up to a 4 x 4 matrix. $\endgroup$
    – Bee
    Oct 22, 2021 at 3:24
0
$\begingroup$

I am sure that, in the second case too, the relation (*) $(I-X^T)^{-1}\circ X=0$ characterizes the acyclic graphs but I have no proof.

Yet, if you want only a characterization of acyclic graphs, then Case 2 is useless.

Indeed, let $X$ be the weight matrix associated to the given graph $\Gamma$ and $a>0$. Then $X$ is nilpotent iff $aX$ is nilpotent.

Note that $\rho(X)\leq u=\max_i \sum_j x_{i,j}$. Thus we choose $a=\dfrac{1}{u+1}$ and we put $X:=aX$.

Thus $\rho(X)<1$ and it remains to test the above relation (*).

The calculation of $u$ has complexity $O(n^2)$ and the one of $(I-X^T)^{-1}\circ X$ is $\sim n^3$.

Finally the global complexity of the test is $\sim n^3$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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