Show a matrix is non-singular and symmetric indefinite

Question

Consider a matrix $A\in \mathbb{R}^{m\times n }$ with $m>n$ is of full column rank. Show that $$B=\begin{bmatrix} I & A \\ A^\top & 0 \end{bmatrix}$$ is non-singular and symmetric indefinite. Also show that the condition number of $B$ is upper bounded by $C\sqrt{\text{Cond}(A^\top A)}$ for some universal constant $C>0$. ($\text{Cond}(A^\top A)$ is the condition number of $A^\top A$).

Any hint would be appreciated!

Answer 1

• Hint about non singularity: use Schur's determinant formula

saying that, when $A$ is invertible (which is the case here): $${\displaystyle M=\left[{\begin{matrix}A&B\\C&D\end{matrix}}\right]} \ \implies \ \det(M)=\det(A)\det \left(D-CA^{-1}B\right)$$

• about indefiniteness, setting $X:=\binom{U}{V}$:

$$X^TMX=\left[{\begin{matrix}U^T&V^T\end{matrix}}\right]\left[{\begin{matrix}I&A\\A^T&0\end{matrix}}\right]\left[{\begin{matrix}U\\V\end{matrix}}\right]=U^TIU+\underbrace{U^TAV+V^TA^TU}_{2(U^TAV) \in \mathbb R}$$

with $U$ and $V$ that can be chosen such as the result is either positive, zero or negative.

• About condition number, the best is to use singular values of $A$.

Answer 2

A hint regarding the condition number: let $A = U \Sigma V^T$ be a singular value decomposition of $A$. Note that $B$ is orthogonally similar to the matrix $$ M = \pmatrix{U & 0\\0 & V}^T \pmatrix{I & A\\ A^T & 0} \pmatrix{U & 0\\ 0 & V} = \pmatrix{I & \Sigma\\ \Sigma^T & 0}. $$ So, $B$ will have the same condition number as $M$. On the other hand, we can use another orthogonal similarity (in particular, a permutation similarity) to put $M$ into a block diagonal form. In particular: if $\sigma_1,\dots,\sigma_n$ denote the singular values of $A$, then there exists a permutation matrix $P$ such that $P^TMP$ is the block diagonal matrix $$ P^TMP = \pmatrix{M_1 \\ & \ddots \\ && M_n\\ &&& I}, \quad \text{where } M_k = \pmatrix{1 & \sigma_k\\ \sigma_k & 0}. $$ The singular values of $B$ are therefore equal to the singular values of each $2 \times 2$ matrix $M_k$ along with $1$.