Sufficient conditions for invertibility of a block tridiagonal matrix

Question

Let $M_n \in \mathbb{R}^{N \times N}$ be a block-tridiagonal matrix:

$$M_n = \begin{bmatrix} B_1 & C_1 & 0 & 0 & \cdots & 0 \\ A_1 & B_2 & C_2 & 0 & \cdots & 0 \\ 0 & A_2 & B_3 & C_3 & \cdots & 0 \\ 0 & 0 & A_3 & B_4 & \ddots & \vdots \\ \vdots & \vdots & \vdots & \ddots & \ddots & C_{n - 1} \\ 0 & 0 & \cdots & 0 & A_{n - 1} & B_n \end{bmatrix} $$

where each $B_i \in \mathbb{R}^{m_i \times m_i}$ is square and invertible, with varying sizes; $A_i$ and $C_i$ may not be square.

Problem

What are sufficient conditions on $A_i$, $B_i$ and $C_i$ for showing that $M_n$ is invertible?

Strategies

The following is a list of strategies for approaching the problem; i.e. starting points. They are not answers to the problem, because they depend on $D_i$.

Simplifying blocks

Without loss of generality, we may assume $B_i = I$; $M_n$ is invertible if and only if $\lceil B_1^{-1}, \dots, B_n^{-1} \rfloor M_n$ is invertible.

Block-LDU-decomposition

Let

$$ \begin{aligned} D_1 & = I, \\ D_{i + 1} & = I - A_i D_i^{-1} C_i, \\ L_i & = A_i D_i^{-1}, \\ U_i & = D_i^{-1} C_i. \end{aligned} $$

Supposing each $D_i$ is invertible, $M_n$ has the block-LDU-decomposition $M_n = LDU$, where:

$$L = \begin{bmatrix} I & 0 & 0 & 0 & \cdots & 0 \\ L_1 & I & 0 & 0 & \cdots & 0 \\ 0 & L_2 & I & 0& \cdots & 0 \\ 0 & 0 & L_3 & I & \ddots & \vdots \\ \vdots & \vdots & \vdots & \ddots & \ddots & 0 \\ 0 & 0 & \cdots & 0 & L_{n - 1} & I \end{bmatrix},$$ $$U = \begin{bmatrix} I & U_1 & 0 & 0 & \cdots & 0 \\ 0 & I & U_2 & 0 & \cdots & 0 \\ 0 & 0 & I & U_3 & \cdots & 0 \\ 0 & 0 & 0 & I & \ddots & \vdots \\ \vdots & \vdots & \vdots & \ddots & \ddots & U_{n - 1} \\ 0 & 0 & \cdots & 0 & 0 & I \end{bmatrix},$$ $$D = \lceil D_1, \dots, D_n \rfloor.$$

Then

$$\det(M_n) = \prod_{i = 1}^n \det(D_i).$$

Hence invertibility of each $D_i$ implies $M_n$ is invertible.

Equivalents

In fact, the following are equivalent:

• $M_n$ is invertible,
• each $D_i$ is invertible,
• $M_i$ is invertible for each $1 \leq i \leq n$.

This is in contrast to general block matrices which may require pivoting to complete an LDU-decomposition.

Eigenvalues

Eigenvalues provide an equivalent condition (by Weinstein–Aronszajn identity and generalized Schur decomposition): $$ \begin{aligned} {} & \Lambda(D_i) \cap \Lambda(C_i A_i) = \emptyset \\ \iff & \det(D_i - C_i A_i) \neq 0 \\ \iff & \det(I - D_i^{-1} C_i A_i) \neq 0 \\ \iff & \det(I - A_i D_i^{-1} C_i) \neq 0 \\ \iff & \det(D_{i + 1}) \neq 0. \end{aligned} $$ where $\Lambda(X)$ is the set of eigenvalues of $X$.

Singular values

Singular values provide a sufficient condition: $$ \begin{aligned} {} & \sigma(D_i) \cap \sigma(C_i A_i) = \emptyset \\ \iff & \det((C_i A_i)^T C_i A_i - D_i^T D_i) \neq 0 \\ \iff & \det((C_i A_i D_i^{-1})^T C_i A_i D_i^{-1} - I) \neq 0 \\ \iff & 1 \not\in \sigma(C_i A_i D_i^{-1}) \\ \implies & 1 \not\in \Lambda(C_i A_i D_i^{-1}) \\ \iff & \det(I - C_i A_i D_i^{-1}) \neq 0 \\ \iff & \det(I - A_i D_i^{-1} C_i) \neq 0 \\ \iff & \det(D_{i + 1}) \neq 0, \end{aligned} $$ where $\sigma(X)$ is the set of singular values of $X$.

Principal minors

Principal minors provide an equivalent condition.

The determinant of a sum of matrices $X, Y \in \mathbb{R}^{N \times N}$ is

$$\det(X + Y) = \sum_{n = 0}^N \sum_{I, J \subset_n N} \det(A_{I, J}) \det(B_{N \setminus I, N \setminus J}) (-1)^{\sum I + \sum J},$$

where $I$ and $J$ are strictly increasing sequences of length $n$.

When $Y = I$, this simplifies to

$$\det(X + I) = \sum_{I \subset N} \det(X_{I, I}).$$

Hence, $$\begin{aligned} \det(D_{i + 1}) & = \det(I - A_i D_i^{-1} C_i) \\ {} & = \det(I) \det(I - D_i^{-1} C_i A_i) \\ {} & = \det(I) \sum_{I \subset N} \det((-D_i^{-1} C_i A_i)_{I, I}). \end{aligned}$$

The minor of a product of matrices $X \in \mathbb{R}^{M \times N}$ and $Y \in \mathbb{R}^{N \times P}$ is:

$$\det((XY)_{I, J}) = \sum_{K \subset_{|I|}} \det(A_{I, K}) \det(B_{K, J}),$$

where $I \subset M$, $J \subset P$, and $|I| = |J|$. Hence $$ \det(D_{i + 1}) = \det(I) \sum_{I \subset N} \sum_{K \subset_{|I|} N} \det((D_i^{-1})_{I, K}) \det((-C_i A_i)_{K, I}).$$

Schur complements

The matrix $D_{i + 1}$ is a Schur complement.

Hence sufficient conditions for the invertibility of Schur complements can be useful.

Simplifying sizes

Each block $B_i$ can be replaced with $\lceil B_i, I \rfloor$, where $I$ is an identity matrix of appropriate size, to bring the diagonal blocks to same size. Similarly, each $A_i$ is appended zero rows, and each $C_i$ is appended zero columns. This extended matrix is invertible if and only if $M_n$ is. Hence, sufficient conditions for when each $B_i$ has the same size can also be helpful.

Test matrix

The following matrix is an example of a matrix which I would like the condition to cover. Let

$$A_i = \begin{bmatrix} -1/8 & 0 & 0 & 0 \\ -1/8 & 0 & 0 & 0 \\ -1/4 & 0 & 0 & 0 \\ -1/2 & 0 & 0 & 0 \\ \end{bmatrix}$$ $$C_i = \begin{bmatrix} 0 & -1/8 & 3/4 & -3/2 \\ 0 & -1/8 & 3/4 & -3/2 \\ 0 & -1/4 & 3/2 & -2 \\ 0 & -1/2 & 2 & -2 \\ \end{bmatrix}$$

Then $M_n$ is invertible, but not block-diagonally dominant ($|A_i| \approx 4.45 > 1$), $C_i \neq 0$, and $C_i A_i \neq 0$. The eigenvalues of $C_i A_i$ are $\{37/64 \approx 0.58, 0, 0, 0\}$. Numerical tests suggest that each eigenvalue of each $M_n$ is real and in the range $(0, 2]$, $\det(M_n) > 0$, and $\det(M_n) \to 0$.

The following matrices are such that $C_i A_i$ has irrational eigenvalues: $$A_i = \begin{bmatrix} 0 & 0 & 1/4 & -1 \\ 0 & 0 & 1/4 & -3/4 \\ 0 & 0 & 1/4 & -3/4 \\ 0 & 0 & 1/4 & -1/2 \\ \end{bmatrix}$$ $$C_i = \begin{bmatrix} -1/2 & 1/4 & 0 & 0 \\ -3/4 & 1/4 & 0 & 0 \\ -3/4 & 1/4 & 0 & 0 \\ -1 & 1/4 & 0 & 0 \\ \end{bmatrix}$$ $\Lambda(C_i A_i) = (0, 0, \approx 0.00572957, \approx 0.68177043)$

Non-invertible test matrix

The following is an example of how easy it is to get a non-invertible block matrix. Let $A_i = C_i = (1/\sqrt{2}) e_1 e_1^T$. Then $\det(M_n) = 0$ for each $n > 2$, while $\det(M_n) = 1 / 2$ for $n = 2$.

Answer 1

The following is a list of answers I know for some specific cases. However, they are not strong enough for my uses.

Simple conditions

• A sufficient, but weak condition is that $C_i = 0$ for each $i$.
• Slightly stronger sufficient condition is $A_i C_i = 0$ for each $1 \leq i < n$. Then $D_i = I$, and so $\det(M) = \prod_{i = 1}^n \det(I) = 1 \neq 0$.

Conditions for general block matrices

Let $M$ be any block matrix $M = [A_{i,j}]$ consisting of blocks $A_{i, j}$. The following are general results which do not depend on the block-tridiagonal structure, but do require that each $A_{i, i}$ is invertible.

• The paper Block diagonally dominant matrices and generalizations of the Gerschgorin circle theorem shows that $M$ is invertible if $M$ is strictly block-diagonally dominant, i.e. $\sum_{i \neq j} ||A_{i, i}^{-1}|| ||A_{i, j}|| < 1$. The paper also contains a slightly stronger result.
• The paper Block diagonal dominance of matrices revisited: Bounds for the norms of inverses and eigenvalue inclusion sets shows that $M$ is invertible if
  • $\sum_{j \neq i} ||A_{i,i}^{-1} A_{i,j}|| < 1$,
  • $\sum_{j \neq i} ||A_{i,j} A_{i,i}^{-1}|| < 1$.
• The previous is also strict block-diagonal dominance, but a more general definition.

Conditions for tridiagonal matrices

The following conditions are for tridiagonal matrices; i.e. $m_i = 1$ for each $i$.

The paper Tridiagonal matrices: invertibility and conditioning shows that if $A_i C_i \leq 1 / 4$, and $m = \min_i \{(1 + \sqrt{1 - 4 A_i C_i}) / 2\} > 0$, then $D_i \geq m$; i.e. $M$ is invertible. In particular, this condition covers matrices which may not be strictly diagonally dominated.

Answer 2

This is a partial answer. These theorems are still too weak to cover the given test matrix.

The following theorems generalize those in Tridiagonal matrices: inversion and conditioning

• to all rational eigenvalues except $1, 1/2, 1/3$,
• to complex eigenvalues,
• to block-tridiagonal matrices.

$\newcommand{\imag}[1]{\mathrm{im}({#1})} \newcommand{\real}[1]{\mathrm{re}({#1})}$

Background and notation

A tridiagonal iteration is $f_{\lambda} : \mathbb{C} \to \mathbb{C}$, where $\lambda \in \mathbb{C}$, such that

$$f_{\lambda}(x) = 1 - \lambda / x,$$ $$f_{\lambda}(0) = 0.$$

A subset $R \subset \mathbb{C}$ is $\Lambda$-invariant, where $\Lambda \subset \mathbb{C}$, if

• $0 \not\in R$,
• $1 \in R$,
• $f_{\lambda}(R) \subset R$ for each $\lambda \in \Lambda$.

I'll abbreviate $\lambda$-invariant for $\{\lambda\}$-invariant.

Let $\Lambda(X)$ denote the set of eigenvalues of $X$. We shall make use of the following properties of eigenvalues:

• $\Lambda(AB) \subset \Lambda(A) \Lambda(B)$ for any invertible $B$. This can be seen by the generalized Schur decomposition.
• If $\Lambda(A), \Lambda(B) \subset \mathbb{R}$, then also $\Lambda(AB) \subset \mathbb{R}$.
• $\Lambda(AB) = \Lambda(BA)$. This can be seen by the Weinstein–Aronszajn identity.
• $\Lambda(B^{-1}) = \Lambda(B)^{-1}$ for any invertible $B$,

Let

$$\mathbb{T} = \{x \in \mathbb{R} : x \text{ is transcendental}\},$$ $$\hat{\mathbb{Q}} = \mathbb{Q} \setminus \{1, 1/2, 1/3\},$$ $$\hat{\mathbb{C}} = (\mathbb{C} \setminus \mathbb{R}^{> 1/4}) \cup \hat{\mathbb{Q}} \cup \mathbb{T},$$ $$\Lambda^* = \bigcup_i \Lambda(C_i A_i).$$

Without loss of generality, we may assume $B_i = I$.

Theorem (Real tridiagonal iteration)

Let $\Lambda \subset \mathbb{R}^{\leq 1 / 4}$ be finite. Then there exists $\Lambda$-invariant $R \subset \mathbb{C}$.

Proof

This proof is more or less a copy from Tridiagonal matrices: inversion and conditioning. We will first show that $R$ is $\lambda$-invariant for $\lambda \in \Lambda$.

Suppose $\lambda \leq 0$ and $x > 0$. Then $f_{\lambda}(x) = 1 - \lambda / x \geq 1$, and we may pick $R_{\lambda} = \mathbb{R}^{\geq \alpha_{\lambda}}$, where $\alpha_{\lambda} = 1$.

Suppose $0 < \lambda \leq 1 / 4$. Let $\Delta = \sqrt{1 - 4\lambda}$, $r_1 = (1 - \Delta) / 2$, $r_2 = (1 + \Delta) / 2$, and $\alpha_{\lambda} \in [r_1, r_2]$. We have $$\begin{aligned} {} & r_1 > 0 \land r_2 < 1 \\ \iff & \lambda > 0. \end{aligned}$$ Therefore $1 \geq r_2 \geq \alpha_{\lambda} \geq r_1 > 0$. We have $$\begin{aligned} {} & f_{\lambda}(x) = x \\ \iff & 1 - \lambda / x = x \\ \iff & x^2 - x + \lambda = 0 \\ \iff & x \in \{r_1, r_2\}. \end{aligned}$$ Therefore $$\begin{aligned} {} & x \in [r_1, r_2] \\ \iff & x^2 - x + \lambda \leq 0 \\ \iff & 1 - \lambda / x \geq x \\ \iff & f_{\lambda}(x) \geq x. \end{aligned}$$ Therefore $f_{\lambda}(\alpha_{\lambda}) \geq \alpha_{\lambda}$. We have $$\begin{aligned} f'(x) = \lambda x^{-2}. \end{aligned}$$ Therefore $f$ is increasing when $x > 0$, and $$\begin{aligned} f_{\lambda}(x) \geq f_{\lambda}(\alpha_{\lambda}) \geq \alpha_{\lambda} \end{aligned}$$ for each $x \geq \alpha_{\lambda}$. That is, we may pick $R_{\lambda} = \mathbb{R}^{\geq \alpha_{\lambda}}$.

Finally, let $R = \bigcup_{\lambda} R_{\lambda}$.

Theorem (Explicit formula for iteration)

Let $$\begin{aligned} a_n = \sum_{i = 0}^{\lfloor n / 2 \rfloor} \binom{n-i}{i} (-\lambda)^i. \end{aligned}$$ Then $$\begin{aligned} f_{\lambda}^n(1) & = a_{n + 1} / a_n. \end{aligned}$$

Theorem (Rational tridiagonal iteration)

Suppose $\lambda \in \mathbb{Q}$. Then $f_{\lambda}^n(1) \neq 0$ for each $n \in \mathbb{N}$ if and only if $\lambda \not\in \{1, 1/2, 1/3\}$.

Proof

Let $p, r \in \mathbb{Z}$, and $\lambda = p / r$. Suppose $p = 0$ and $r = 1$. Then $f_{\lambda}^n(1) = 1$ for each $n \in \mathbb{N}$. Suppose $p$ and $r$ are coprime, and $p \neq 1$. It suffices to study when $a_n = 0$ in the explicit formula for the iteration. Suppose $$\begin{aligned} {} & a_n = 0 \\ \iff & \sum_{i = 0}^{\lfloor n / 2 \rfloor} \binom{n-i}{i} (-p/r)^i = 0 \\ \iff & \sum_{i = 0}^{\lfloor n / 2 \rfloor} \binom{n-i}{i} (-p)^i r^{\lfloor n / 2 \rfloor - i} = 0. \end{aligned}$$ Taking modulo $p$ from both sides shows that $$\begin{aligned} r^{\lfloor n / 2 \rfloor} = mp \end{aligned}$$ for some $m \in \mathbb{N}^{> 0}$. Then $p$ divides $r$, so that $p$ and $r$ are not coprime. Therefore $a_n \neq 0$.

Suppose $p = 1$. By "Real tridiagonal iteration" theorem, we know that the result holds for $|r| >= 4$. The sequence for $r = 1$ is $(1, 0)$, for $r = 2$ is $(1, 1/2, 0)$, and for $r = 3$ is $(1, 2/3, 1/2, 1/3, 0)$.

Theorem (Transcendental tridiagonal iteration)

Suppose $\lambda \in \mathbb{C}$ is transcendental. Then $f_{\lambda}^n(1) \neq 0$ for each $n \in \mathbb{N}$.

Proof

The explicit formula for the iteration shows that $f^n(1)$ is a ratio of polynomials with integer coefficients. Hence $f^n(1) = 0$ for some $n$ implies that $c$ is algebraic.

Note (Irrational tridiagonal iteration)

Let $\lambda = 3/2 + \sqrt{5}/2$. Then $f^n(1)$ reaches zero with sequence $(1, -\sqrt(5)/2 - 1/2, 1 + (\sqrt(5) + 3)/(\sqrt(5) + 1), 0)$. Similarly for $\lambda = 3/2 - \sqrt{5}/2$.

Theorem (Complex tridiagonal double-iteration)

Let $\lambda \in \mathbb{C}$, and $\imag{\lambda} > 0$. Then $\imag{f_{\lambda}^2(x)} < 0$ for each $x \in \mathbb{C} \setminus \{0\}$ such that $\imag{x} \leq 0$. In addition, the theorem holds after transposing each comparison.

Proof

Let $$\begin{aligned} \lambda & = a + ib, \\ x & = c + id, \\ u & = 1 - \frac{ac + bd}{c^2 + d^2}, \\ v & = \frac{ad - bc}{c^2 + d^2}. \end{aligned}$$ Then $$\begin{aligned} f_{\lambda}(x) & = 1 - \lambda / x \\ {} & = 1 - \lambda x^* / |x|^2 \\ {} & = u + iv. \end{aligned}$$ By assumption, $b > 0$ and $d \leq 0$. Then $$\begin{aligned} {} & \imag{f_{\lambda}^2(x)} < 0 \\ \iff & av < bu \\ \iff & a \frac{ad - bc}{c^2 + d^2} < b - b\frac{ac + bd}{c^2 + d^2} \\ \iff & a (ad - bc) < b (c^2 + d^2) - b (ac + bd) \\ \iff & a^2 d - abc < b (c^2 + d^2) - abc - b^2d \\ \iff & a^2 d < b (c^2 + d^2) - b^2d \\ \iff & d(a^2 + b^2) < b(c^2 + d^2) \\ \iff & \mathrm{true}. \end{aligned}$$

Corollary (Complex tridiagonal iteration)

Let $\lambda \in \mathbb{C}$, and $\imag{\lambda} > 0$. Then $\imag{f_{\lambda}^n(1)} < 0$ for each $n \in \mathbb{N}^{> 0}$. In addition, the theorem holds after transposing each comparison.

Corollary (Tridiagonal iteration)

Let $\lambda \in \hat{\mathbb{C}}$. Then $f_{\lambda}^n(1) \neq 0$ for each $n \in \mathbb{N}^{>0}$.

Corollary (Tridiagonal Toeplitz invertibility)

Suppose each $m_i = 1$ and $C_i A_i = \lambda \in \hat{\mathbb{C}}$. Then $M_n$ is invertible. In particular, this covers tridiagonal Toeplitz matrices.

Theorem (Block-tridiagonal iteration)

Let $F_i(X) = I - A_i X^{-1} C_i$ for invertible $X$, $F_i(X) = X$ for non-invertible $X$, and $R \subset \mathbb{C}$ be $\Lambda^*$-invariant. Then $\Lambda(F_i(X)) \subset R$ for each $X$ such that $\Lambda(X) \subset R$.

Proof

Suppose $\Lambda(X) \subset R$. Then $$\begin{aligned} \Lambda(F_i(X)) & = \Lambda(I - A_i X^{-1} C_i) \\ {} & = 1 - \Lambda(A_i X^{-1} C_i) \\ {} & = 1 - \Lambda(C_i A_i X^{-1}) \\ {} & \subset \{1 - \lambda / x : \lambda \in \Lambda(C_i A_i), x \in \Lambda(X)\} \\ {} & = \{f_{\lambda}(x) : \lambda \in \Lambda(C_i A_i), x \in \Lambda(X)\} \\ {} & \subset R. \end{aligned}$$

Corollary (Block-tridiagonal invertibility)

Suppose there exists $\Lambda^*$-invariant $R \subset \mathbb{C}$. Then $M$ is invertible. For example, right now this holds when $\Lambda^* \leq 1 / 4$.