Given a matrix $A \in R^{m \times n}$ with known upper bound on the operatornorm $\| A \|$ I want to find an upper bound for the operator norm of the square root of the following matrix that is given as
$$
M = \begin{pmatrix} \alpha I_n & -A^T \\ -A & \beta I_m \end{pmatrix} \in R^{(n+m) \times (n+m)}
$$.
where $I_n$ and $I_m$ denote the $n$ respectively $m$ dimensional identity matrix. Furthermore, we have that M is symmetric and positive definite.
So I'm looking for an upper bound of
$\| M^{\frac{1}{2}} \| = \underset{\|z\|=1} \sup \sqrt{ z^T M z }$ in terms of $\alpha$, $\beta$ and $\| A \|$.
Is there some theorem that gives a good estimate for matrices with this kind of special block/diagonal structure? I didn't get very far by manual calculation.
Best Answer
Let $A=U\tilde{\Sigma}V^T$ be the SVD of the rank-$r$ matrix $A$ with $$ \tilde{\Sigma}=\begin{bmatrix}\Sigma_r&0_{r\times(n-r)}\\0_{(m-r)\times r}&0_{(m-r)\times(n-r)}\end{bmatrix}\in\mathbb{R}^{m\times n}, $$ where $\Sigma_r=\mathrm{diag}(\sigma_1,\ldots,\sigma_r)$ is diagonal with the nonzero singular values of $A$ on the diagonal. The matrix $M$ is orthogonally similar (hint: consider the block diagonal matrix with diagonal blocks $V$ and $U$) to $$ N=\begin{bmatrix} \alpha I_r & 0_{r\times(n-r)} & -\Sigma_r & 0_{r\times(m-r)} \\ 0_{(n-r)\times r} & \alpha I_{n-r} & 0_{(n-r)\times r} & 0_{(n-r)\times(m-r)} \\ -\Sigma_r & 0_{r\times(n-r)} & \beta I_r & 0_{r\times(m-r)} \\ 0_{(m-r)\times r} & 0_{(m-r)\times(n-r)} & 0_{(m-r)\times r} & \beta I_{m-r} \end{bmatrix}. $$ Now you can see the spectrum of $N$ (and hence the spectrum of $M$) consists of the eigenvalues of $2\times 2$ matrices $$ \begin{bmatrix} \alpha & -\sigma_i \\ -\sigma_i & \beta \end{bmatrix}, \quad i=1,\ldots,r. $$ The spectrum of $M$ may also contain $\alpha$ (if $r<n$) and/or $\beta$ (if $r<m$). From here, you can find your operator norm of $M$ (and $M^{1/2}$ as well).