When is $(I - X)^{-\top} \circ X = 0$?

Question

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.

Answer 1

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

Answer 2

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