Why may a matrix be singular or ill-conditioned with standard learning algorithm for linear classification? In the learning algorithm for linear classification by least square method, which find a weight vector $\hat w\in R^d$ and bias $\hat b\in R$ for a linear scoring function $f(x) = \hat w ^T x +\hat b$ for which may write the solution for $\hat w =[\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)^T]^{-1}\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)$, why may the matrix $\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)^T$ be singular or ill-conditioned ? What does that mean to be ill-conditioned ? why does it occurs when $n$ is less than the dimension of $x$ ?
 A: $\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)^T$ is a $d$ by $d$ matrix, where $x$ is a $d$ by $1$ vector.  
For each $i$, $(x_i-\bar x)(x_i -\bar x)^T$ is a $d$ by $d$ matrix.  This matrix is rank one, because it is the outer product of a vector with itself.  $\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)^T$ is the sum of $n$ rank one matrices, and therefore has a rank not exceeding $n$.  If $n < d$, $\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)^T$ must therefore be singular, because it can not be of full rank k. 
In a sense, singular is the most ill-conditioned a matrix can be, having condition number = $\infty$.  Even if $\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)^T$ is not singular, which can only be the case if $n \ge d$, it may still be ill-conditioned, thereby resulting in numerically unstable and very sensitive calculations when it is inverted or used in a linear system of equations. There are shrinkage estimators (search on this site and on the internet) to try to improve the conditioning of (sample) covariance matrices.  $\sum^n_{i=1}(x_i-\bar x)(x_i -\bar x)^T$ is the sample covariance matrix, other than not dividing by $n$ or $n-1$; note that dividing by $n$ or $n-1$ does not affect the rank vs not dividing at all.
