# Bounding the minimum singular value of a block triangular matrix

Question:

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?

Some known bounds:

Since the minimum singular value of $M$ is one over the norm of $M^{-1}$, we can equivalently look for upper bounds on $M^{-1}$, which has the following block structure: $$M^{-1} = \begin{bmatrix} A^{-1} & -A^{-1}BD^{-1} \\ 0 & D^{-1} \end{bmatrix}.$$

Applying the triangle inequality yields the simple bound: $$\left\Vert M^{-1} \right\Vert \le \left\Vert D^{-1} \right\Vert + \left\Vert A^{-1}BD^{-1} \right\Vert + \left\Vert A^{-1} \right\Vert,$$

A slightly more involved argument discussed here yields the (usually sharper) bounds: \begin{align} \left\Vert M^{-1} \right\Vert &\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} \\ \left\Vert M^{-1} \right\Vert &\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}. \end{align}

Conjecture:

The obvious conjecture is the following symmetrized version: $$\left\Vert M^{-1} \right\Vert \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.

Notes:

• Presumably this has been systematically studied somewhere, but I have just been unable to find the right paper.

• Perhaps there is no one "best" bound. In that case, it would still be useful to know what different bounds are out there, and what the tradeoffs are between them.

• Since $M^{-1}$ has the same structure as $M$, you could just state your claims in terms of $M$ directly. Mar 30, 2017 at 0:52

Yes, this works. As I suggested in my comment above, we can rephrase the claim as $\|M\|^2 \le \|A\|^2 + \|B\|^2 + \|D\|^2$, and this we can check by direct calculation: Apply $M$ to $v=(x,y)^t$. Then $$\|Mv\|^2 =\|Ax+By\|^2 + \|Dy\|^2$$ and $$\|Ax+By\|^2 \le (\|A\| \|x\|+\|B\|\|y\|)^2 \le (\|A\|^2 + \|B\|^2)(\|x\|^2+\|y\|^2) ,$$ (by the Cauchy-Schwarz inequality on $\mathbb R^2$ in the last step) as desired.

• Nice to see this direct answer! I guess your answer came in while I was typing mine :-) Mar 30, 2017 at 1:16

It suffices to state the bound for $M$, as also noted in C. Remling's comment.

In particular, recall that $\|M\|^2 = \|M^*M\|$, whereby we have the bound \begin{equation*} \|M\|^2 = \left\|\begin{bmatrix} A^*A + B^*B & B^*D\\ D^*B & D^*D \end{bmatrix}\right\| \le \|A^*A + B^*B + D^*D\|, \end{equation*} where the final inequality holds as the block matrix involved is PSD.

One can even prove related bounds if norms other than the operator norm are desired. See for instance this interesting paper by K. Audenaert for bounds involving Schatten-$p$ norms (though it leads to somewhat different inequalities); while Bourin's paper provides such inequalities for all symmetric (i.e., unitarily invariant) norms.

• That's what I tried first, but I didn't know enough theory... Mar 30, 2017 at 1:20
• Err, i don't understand the inequality. What if A and D are different size matrices? Mar 30, 2017 at 2:04
• If they are different sized, then indeed it does not apply out of the box (and you'd have to pad them with zeros to make them obtain the same size) Mar 30, 2017 at 3:55