What is the sharpest known lower bound for the minimum singular value of the block triangular matrix $$M:=\begin{bmatrix} A & B \\ 0 & D \end{bmatrix}$$ in terms of the properties of its constituent matrices?


  • Block triangular matrices are ubiquitous in numerical linear algebra, and the minimum singular value is a basic property of any matrix. So, it would be useful to have a canonical answer to this question in an easily searchable place on the internet.

  • A matrix of this form came up in my research on numerical methods, and I need to estimate its minimum singular value in order to understand the stability of a method I'm working on.

My bound:

I was able to come up with the bounds $$\boxed{\frac{1}{\sigma_\text{min}(M)} \le \sqrt{\left\Vert A^{-1}\right\Vert^2\left(1 + \left\Vert BD^{-1} \right\Vert^2 \right) + \left\Vert D^{-1} \right\Vert^2}}$$ and $$\boxed{\frac{1}{\sigma_\text{min}(M)} \le \sqrt{\left\Vert D^{-1}\right\Vert^2\left(1 + \left\Vert A^{-1}B \right\Vert^2 \right) + \left\Vert A^{-1} \right\Vert^2}.}$$ using the following argument (for the first bound, the second one is the same argument but on the transpose):

The minimum singular value of a matrix is the inverse of the norm of the inverse matrix: $$\frac{1}{\sigma_\text{min}(M)} = \left\Vert M^{-1} \right\Vert.$$ But inverse of a block triangular matrix has the following exact formula: $$M^{-1} = \begin{bmatrix} A^{-1} & -A^{-1}BD^{-1} \\ 0 & D^{-1} \end{bmatrix}.$$ Estimating the norm of the inverse directly from the definition and using the submultiplicative property of norms yields the boxed bound above: \begin{align*} \left\Vert M^{-1} \right\Vert^2 &= \sup_{||u||^2+||v||^2=1} \left\Vert \begin{bmatrix} A^{-1} & -A^{-1}BD^{-1} \\ 0 & D^{-1} \end{bmatrix} \begin{bmatrix}u \\ v\end{bmatrix} \right\Vert^2 \\ &= \sup_{||u||^2+||v||^2=1} \left\Vert A^{-1} u - A^{-1}BD^{-1}v \right\Vert^2 + \left\Vert D^{-1} v\right\Vert^2 \\ &\le \left\Vert A^{-1}\right\Vert^2 \left\Vert\begin{bmatrix}I & -BD^{-1}\end{bmatrix}\right\Vert^2 + \left\Vert D^{-1} \right\Vert^2 \\ &= \left\Vert A^{-1}\right\Vert^2\left(1 + \left\Vert BD^{-1} \right\Vert^2 \right) + \left\Vert D^{-1} \right\Vert^2. \end{align*}

Conjectured bound:

The obvious conjecture based on the two bounds above is the following symmetrized version: $$\frac{1}{\sigma_\text{min}(M)} \overset{?}{\le} \sqrt{\left\Vert D^{-1} \right\Vert^2 + \left\Vert A^{-1}BD^{-1} \right\Vert ^2 + \left\Vert A^{-1} \right\Vert ^2},$$ which I have been unable to prove.

If one applies the triangle inequality to the blocks of $M^{-1}$, one gets the similar looking bound: $$\frac{1}{\sigma_\text{min}(M)} \le \left\Vert D^{-1} \right\Vert + \left\Vert A^{-1}BD^{-1} \right\Vert + \left\Vert A^{-1} \right\Vert,$$ but this is strictly worse than the conjectured bound since it is a sum rather than the square root of a sum of squares.


After getting no answers here, I posted on mathoverflow, where it was answered. The conjectured bound is true.



You must log in to answer this question.