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
Best Answer
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.