How to prove that block matrix may be ill conditioned

Question

I'm trying to understand why the follow matrix may be ill-conditioned

$$ \left[\begin{array}{cc}{X^{\top} X+\frac{1}{\gamma} I} & {X^{\top} e} \\ {e^{\top} X} & {e^{\top} e}\end{array}\right] $$

where $X \in \mathbb{R^{m \times n}} \, m \ll n$, $\gamma > 0$, $e = [1, \ldots,1]^T \in \mathbb{R^m}$

and the solution of the following system may be not unique

$$ \left[\begin{array}{cc}{X^{\top} X+\frac{1}{\gamma} I} & {X^{\top} e} \\ {e^{\top} X} & {e^{\top} e}\end{array}\right]\left[\begin{array}{l}{w} \\ {b}\end{array}\right]=\left[\begin{array}{c}{X^{\top}} \\ {e^{\top}}\end{array}\right] Y e $$ where $Y \in \mathbb{R^{m\times m}}$ a diagonal matrix, $w \in \mathbb{R^n}$, $b \in \mathbb{R}$

I realize that $rank(X^TX) \leq m \ll n$. I don't know what to do from here. Thanks

Answer 1

Let $M_{\gamma}=\left[\begin{array}{cc}{X^{\top} X+\frac{1}{\gamma} I} & {X^{\top} e} \\ {e^{\top} X} & {m}\end{array}\right] $. $M_{\gamma}$ is a $n+1\times n+1$ symmetric matrix.

We can see that $[u^T,v^T]M_{\gamma}[u^T,v^T]^T\geq 1/\gamma ||u||^2$ where $u\in\mathbb{R}^n,v\in\mathbb{R}$. Then $M_{\gamma}$ is $\geq 0$; moreover we see that the smallest eigenvalue depends on $1/\gamma$.

EDIT. If we remove the block $(1/\gamma) I$, then the obtained matrix $M$ is $Gramm(C_1,\cdots,C_n,e)$, where $X=[C_1,\cdots,C_n]$. A generic $X$ (choose a random $X$), has full rank $m$ ($dim(\ker(X))=n-m$) and $rank(M)=m$. Clearly, if $u\in \ker X$, then $[u^T,0]^T$ is an eigenvector of $M_{\gamma}$ associated to the eigenvalue $1/\gamma$.

In general, there are exactly $n-m$ eigenvalues equal to $1/\gamma$. Note that, if $\gamma$ is large, then the smallest eigenvalue $\lambda_{\min}$ is often $1/\gamma$ but not always. Moreover, the largest eigenvalue $\lambda_{\max}$ varies little when $\gamma$ varies (say $\lambda_{\max}\approx \tau$).

If we consider the condition number of $M$ associated to the spectral norm ($K(M)=\lambda_{\max}/\lambda_{\min}$), then $K(M)\geq \tau\gamma$. Finally, if $\gamma$ is large, then $M$ is ill-conditionned.

Answer 2

Let $A_t =A + {1 \over t} \begin{bmatrix} I & 0 \\ 0 & 0\end{bmatrix}$, where $A$ is symmetric.

Note that $\lim_{t \to \infty} \sigma_\max (A_t) = \sigma_\max(A)$ and $\lim_{t \to \infty} \sigma_\min (A_t) = \sigma_\min(A)$, and so $\lim_{t \to \infty} \operatorname{cond} A_t = \operatorname{cond} A$.

Note that $\lim_{t \downarrow 0} \sigma_\max (t A_t) = 1$ and $\lim_{t \downarrow 0} \sigma_\min (t A_t) = 0$, and so $\lim_{t \downarrow 0} \operatorname{cond} (tA_t) = \lim_{t \downarrow 0} \operatorname{cond} A_t = \infty$.

In the above, $A= \begin{bmatrix} X^TX & X^Te \\ e^T X & e^T e\end{bmatrix}$, and so $\operatorname{cond} A = \infty$.

Hence $A_t$ becomes arbitrarily ill conditioned both for large $t$ and small positive $t$.