Why is $BB^T$ always invertible?

Question

In Karmarkar’s method, we use $$[I - B^T(BB^T)^{-1}B]v$$ Why does $BB^T$ always have an inverse?

---

Karmarkar’s method is applied to an LP in the following form:

$\min z = cx$

subject to

$AX=0$

$x_1 +x_2 +......+ x_n =1$

$X\ge0$

$x =[x_1 ,x_2,.....,x_n]^T$, $A$ is an $m \times n$ matrix, $c = [c_1, c_2, ..... ,c_n]$ ,and 0 is an n-dimensional column vector of zeros. The LP must also satisfy $[\frac{1}{n},\frac{1}{n},.....,\frac{1}{n}]^T$ is feasible , Optimal $z-$value $=0$

B is the $(m * 1) * n$ matrix whose first m rows are A and whose last row is a vector of $1’$s.

$B = \begin{bmatrix}A\\1 \end{bmatrix}$

Answer 1

For a general matrix $B$ this statement is not true, see the example above. But for the Karmarkar algorithm or interior point method you specified the $B$.

If you want to solve the following LP $min \ c^Tx \quad s.t. Ax = 0, e^Tx = n, x \geq 0$ where $x \in \mathbb{R}^n, A \in \mathbb{R}^{m \times n}$ with $n>2, m<n$, $e = (1,...,1)^T \in \mathbb{R}^n$ and with $ rank A = m, Ae = 0$. Let $\bar{x}$ be a feasible point then we define $D = diag(\bar{x})$. The matrix $B$ is defined by $$B = \begin{pmatrix} AD \\ e^T\end{pmatrix} \in \mathbb{R}^{(m+1) \times n}$$ Thus $$BB^T \in \mathbb{R}^{(m+1)\times (m+1)}$$ Then you only have to show that $$rank (B) = m+1$$ since $rank(A) = rank(AA^T)$

To show this we look at the kernel of $B$ and show the kernel is only the zero vector. Let $$0 = B^T\begin{pmatrix} z \\ z_{m+1} \end{pmatrix} = ADz + z_{m+1}e$$ Since $Ae = 0$ we have that $ADA^T z = 0$ since $rank(A) = m$ and $D$ is a positive diagonal matrix. So we have $z = 0$ and it follows that $z_{m+1}$ also has to be zero. Thus we have $$rank(B) = m+1$$ and $BB^T$ has always an inverse under the constraints above.

Answer 2

The statement is not true.

For example if $A= \begin{bmatrix} 2& 3\\1 & 1 \end{bmatrix}$,then $det(BB^T)=0$ so $BB^T$ is not invertible.