Simple to state yet tricky question 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.
 A: 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.
