Problem 1706

Let's find the inverse of $A/4 = I - X$, where all entries in $X$ are either $0$ or $1/4$. We will use the series
$$(I - X)^{-1} = I + X + X^2 + X^3 + \dots$$
First let's prove that this series converges. It suffices to show that the maximum $M$ such that $\|Xw\| \le M\|w\|$ for all column vectors $w$ of $X$ is less than $1$, so the sum of the entries always decrease by a factor smaller than $1$ if you multiply a vector by $X^2$; then we sum the series as $(I+X)(I+X^2+X^4+\dots)$. Notice that every row of $X$ has at most four nonzero entries, all of which are equal to $1/4$. So if $w = (a_1, a_2, \dots, a_n)$ then every entry of $Xw$ is of the form $\frac{a_{r_1}+a_{r_2}+\dots+a_{r_s}}{4}$, $s \le 4$. By the Cauchy-Schwarz inequality, its square is at most $\frac{s}{16}(a_{r_1}^2+a_{r_2}^2+\dots+a_{r_s}^2) \le \frac{a_{r_1}^2+a_{r_2}^2+\dots+a_{r_s}^2}{4}$, with equality if and only if $a_{r_1} = a_{r_2} = \dots = a_{r_s}$ and $s=4$. Summing over all the rows, the sum of squares of the coordinates of $Xw$ is at most $a_1^2 + a_2^2 + \dots + a_n^2 = \|w\|^2$, because all columns of $X$ have at most four nonzero entries. But equality would only happen if all entries $a_i$ are equal and $s=4$ always, which does not happen for, say, the first row. So $M < 1$ and the series converges.

Consider the graph whose vertices are the numbers $v_1, v_2, \dots, v_n$ and we connect $v_i$ and $v_j$ if and only if the entry $x_{ij}$ in $X$ is $1/4$. By the definition of the matrix $A$, this graph has a lattice-like configuration: it can be split in several paths $v_1v_2 \dots v_{n_1-1}$, $v_{k_1}v_{k_1+1} \dots v_{(k+1)n_1-1}$, $1 \le k \le \frac{n}{2}-1$, $v_r v_{r+n_1} v_{r+2n_1} \dots v_{r+n-n_1}$, $1 \le r \le n_1$. It is clear that this graph is connected. Since the entry $m_{ij}$ in $X^k$ is nonzero if and only if there exists a circuit from $i$ to $j$ with $k$ edges, for all $i, j$ there is $k$ such that the corresponding entry $m_{ij}$ in $X^k$ is nonzero. This proves that all entries in the inverse of $A$ is positive.