6
$\begingroup$

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:

  • This question was asked on math.stackexchange where it got many upvotes but no answers.

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

$\endgroup$
  • 1
    $\begingroup$ Since $M^{-1}$ has the same structure as $M$, you could just state your claims in terms of $M$ directly. $\endgroup$ – Christian Remling Mar 30 '17 at 0:52
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice to see this direct answer! I guess your answer came in while I was typing mine :-) $\endgroup$ – Suvrit Mar 30 '17 at 1:16
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's what I tried first, but I didn't know enough theory... $\endgroup$ – Christian Remling Mar 30 '17 at 1:20
  • $\begingroup$ Err, i don't understand the inequality. What if A and D are different size matrices? $\endgroup$ – Nick Alger Mar 30 '17 at 2:04
  • 1
    $\begingroup$ 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) $\endgroup$ – Suvrit Mar 30 '17 at 3:55

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.