Simple to state yet tricky question

482 Views Asked by At

Define $$A=\left[\mathrm I+\sum_{k=1}^{m_1}v_k v_k^T+\sum_{k=1}^{m_2}u_k u_k^T\right]^{-1},$$ where each $u_k$ and $v_k$ is a $0$-$1$ column vector, and for each $1\leq i \leq n$, the $i$th component is $1$ in exactly one of $u$ vectors and in exactly one of $v$ vectors.

Prove that for every $1\leq k \leq m$ if the $i'th$ element of $u_k$ is $1$ then $i$th component of $Au_{k}$ is positive: $$u_{k,i}=1 \implies (Au_{k})_{i}>0 $$

and same thing for $v$ vectors: $$v_{k,i}=1 \implies (Av_k)_i>0$$

I checked this with computer and it seems correct.

1

There are 1 best solutions below

0
On

This problem turned out to be really very hard to solve!

Let $M$ be the $n\times(m_1+m_2)$ matrix such that $$ M_{ij} = \begin{cases} (v_j)_i \text{ if $1\le j\le m_1$} \\ (u_{j-m_1})_i \text{ if $m_1< j\le m_1+m_2$}. \end{cases} $$ An equivalent representation of $M$: $$ M = \left[v_1 \cdots v_{m_1} u_1 \cdots u_{m_2} \right]. $$ One easily sees that \begin{eqnarray} A &\equiv& \left[ I + \sum_{i=1}^{m_1} v_i v_i^T + \sum_{j=1}^{m_2} u_j u_j^T \right]^{-1} \\ &=& (I + M M^T)^{-1}. \end{eqnarray}

The problem is to prove that an entry in $(I+MM^T)^{-1} M$ is positive whenever the corresponding entry in $M$ is positive.

By the Woodbury matrix identity, $$ (I + M M^T)^{-1} = I - M(I + M^TM)^{-1} M^T. $$ Thus, \begin{eqnarray} (I + M M^T)^{-1} M &=& M - M(I + M^T M)^{-1} M^T M \\ &=& M - M (I+M^T M)^{-1} \left((I+M^T M) - I\right) \\ &=& M - M \left( I - (I+M^T M)^{-1}\right) \\ &=& M (I+M^T M)^{-1}. \end{eqnarray} It follows that the statement we wish to prove is equivalent to the statement that $(I + M^T M)^{-1}M^T$ contains a positive entry whenever the corresponding entry of $M^T$ is positive. This equivalent formulation is easier to prove, because it turns out that $I+M^T M$ is a strictly diagonally dominant matrix and we can use some properties of such matrices in our proof.

Direct computation shows that $M^T M$ may be written in the following form: $$ M^T M = \left[\begin{array}{c|c} D_v & X \\ \hline X^T & D_u \end{array}\right] $$ where $D_v$ is $m_1\times m_1$ diagonal, $D_u$ is $m_2\times m_2$ diagonal, $X$ is $m_1\times m_2$, and \begin{eqnarray} (D_v)_{ii} &=& \#\{i: 1\le i\le n \text{ and } v_i = 1\} \\ (D_u)_{ii} &=& \#\{i: 1\le i\le n \text{ and } u_i = 1\} \\ X_{ij} &=& \#\{i: 1\le i\le n \text{ and } v_i = 1 \text{ and } u_j = 1\}. \end{eqnarray} Given these computations, it is easy to see that $I+M^T M$ is strictly diagonally dominant.

It is also obvious that $I+M^TM$ has strictly positive diagonal.

We will apply the following very cool little lemma, which we prove below:

Lemma Suppose $Y$ is an $n\times n$ strictly diagonally dominant matrix with positive diagonal entries. Then $Y$ is invertible by the Levy–Desplanques Theorem. Let $Z=Y^{-1}$. Then for all $i$ and $j\ne i$, $$ Z_{jj} > |Z_{ij}|. $$

To complete the proof of the main proposition, let $x$ be a column of $M^T$ and define $$ A' \equiv (I + M^T M)^{-1} $$ for brevity. By definition, $x$ is a $0-1$ vector containing exactly two $1$'s. Let $i$ and $j$ be these two indices, so $i\ne j$ and $x_i=x_j=1$. Observe \begin{eqnarray} \left(A'x\right)_i &=& A'_{ii} + A'_{ij} = A'_{ii} + A'_{ji} \\ \left(A'x\right)_j &=& A'_{ji} + A'_{jj} = A'_{jj} + A'_{ij}. \end{eqnarray} By the lemma and the properties of $I+M^T M$ proved above, it follows $(A'x)_i>0$ and $(A'x)_j>0$, which completes the proof.

Proof of the Lemma: We first note that for any strictly diagonally dominant matrix $Q$ with positive diagonal entries, $\det(Q)>0$. To see this, consider the mapping $$ f(t) = \det(Q+tI) $$ for all $t\ge 0$. Since $Q+tI$ is strictly diagonally dominant, $f(t)\ne 0$ for all $t\ge 0$ by Levy–Desplanques. Also, it is clear $$ \lim_{t\to\infty} \det(Q + tI) = +\infty $$ Since $f$ is continuous, $f(0) = \det(Q)>0$.

For brevity, let $m=m_1+m_2$. We can compute $Z_{11}$ and $Z_{21}$ by Cramer's Rule: \begin{eqnarray} Z_{11} &=& \frac{\det(Y_{2:m;2:m})}{\det(Y)} \\ Z_{21} &=& -\frac{\det(Y_{2:m;1,3:m})}{\det(Y)}. \end{eqnarray} Define the following two matrices: \begin{eqnarray} M_+ &=& \left[\begin{array}{c|c} Y_{2:m;2} + Y_{2:m;1} & Y_{2:m;3:m}\end{array}\right] \\ M_- &=& \left[\begin{array}{c|c} Y_{2:m;2} - Y_{2:m;1} & Y_{2:m;3:m}\end{array}\right]. \end{eqnarray} By basic properties of determinants and the Cramer's rule calculations above, \begin{eqnarray} Z_{11} - Z_{21} &=& \frac{\det(Y_{2:m;2:m}) + \det(Y_{2:m;1,3:m})}{\det(Y)} \\ &=& \frac{\det(M_+)}{\det(Y)} \end{eqnarray} and \begin{eqnarray} Z_{11} + Z_{21} &=& \frac{\det(Y_{2:m;2:m}) - \det(Y_{2:m;1,3:m})}{\det(Y)} \\ &=& \frac{\det(M_-)}{\det(Y)}. \end{eqnarray} By definition, it is easy to see $M_+$, $M_-$, and $Y$ are all strictly diagonally dominant matrices with positive diagonal, so all have positive determinant. It follows that $Z_{11} + Z_{21}$ and $Z_{11} - Z_{21}$ are both positive, so $Z_{11} > |Z_{21}|$.

We have shown $Z_{11} > |Z_{21}|$. By relabeling vertices, it is easy to see that $Z_{jj} > |Z_{ij}|$ for all $i$ and $j$. This proves the lemma.