4
$\begingroup$

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

$\endgroup$
7
  • 2
    $\begingroup$ Please be aware that every edit of a question or of one of its answers bumps the thread to the front page. This has happened for this thread about 70 times in the last 10 days. Apart from this, this post looks more like a blog post than like an actual question, and -- unlike on other SE sites -- on MathOverflow posting self-answered questions should usually be avoided. $\endgroup$
    – Stefan Kohl
    Apr 15 at 8:36
  • $\begingroup$ Hi Stefan. I had no idea about the bumping, sorry about that! This is not a blog post. The question is still very much open. Nor have I answered my question except for some simple cases which are not strong enough for me. What I have written below is what I have learned and generalized during these 11 days. My hope was that eventually someone would recognize something from them or had ideas where to look at or to see how to generalize the results. It is now beginning to look like the topic has not been resolved before. Does the editing of my answers also bump the question? $\endgroup$
    – kaba
    Apr 15 at 12:11
  • $\begingroup$ I wish there was a way to make non-bumping edits meta.stackexchange.com/questions/23241/… $\endgroup$
    – kaba
    Apr 15 at 12:21
  • $\begingroup$ Yes -- as I said, also editing of your answers bumps the question to the front page. The bumping is mainly a mechanism to ensure that any vandalism to posts (including self-vandalism) will be noticed quickly by the community -- and it would be not good to offer a way to circumvent that safeguard. $\endgroup$
    – Stefan Kohl
    Apr 15 at 12:29
  • 1
    $\begingroup$ I see. Thank you for notifying me. I'll refrain from further edits. $\endgroup$
    – kaba
    Apr 15 at 12:31
0
$\begingroup$

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.

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.