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

2more comments