# Why is $BB^T$ always invertible?

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}$

• i make $BB^T$ , and try to calculate $det (BB^T)$.but calculation of determinent is hard. is there better way ? – yaodao vang Jan 12 '18 at 13:04
• In general, this is false. Take a diagonal matrix with one diagonal entry equals to one and the other entries identically zero. Its transpose is itself and therefore not invertible. – Leandro Jan 12 '18 at 13:06
• As @Omnomnomnom points out below, $BB^T$ is only invertible if the rows of $B$ are linearly independent. In terms of the LP, there must be no redundant or conflicting constraints. – Rahul Jan 12 '18 at 14:41
• If $B = \begin{bmatrix}A'\\1 \end{bmatrix}$ such that $A'=D(X)A$ where D(x) is a diagonal matrix,that make by X. We have always inverse? – yaodao vang Jan 12 '18 at 19:09
• $$D(X)=\begin{bmatrix}‎ ‎\frac{1}{n}&0&0&\cdots & 0\\‎ ‎0&‎\frac{1}{n}&0&\cdots & 0\\‎ 0&0&0&\cdots & ‎\frac{1}{n}\\‎ ‎‎‎\end{bmatrix}$$ – yaodao vang Jan 12 '18 at 19:20

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.
For example if $A= \begin{bmatrix} 2& 3\\1 & 1 \end{bmatrix}$,then $det(BB^T)=0$ so $BB^T$ is not invertible.