6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ i make $BB^T$ , and try to calculate $det (BB^T)$.but calculation of determinent is hard. is there better way ? $\endgroup$ – yaodao vang Jan 12 '18 at 13:04
  • 2
    $\begingroup$ 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. $\endgroup$ – Leandro Jan 12 '18 at 13:06
  • 4
    $\begingroup$ 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. $\endgroup$ – Rahul Jan 12 '18 at 14:41
  • $\begingroup$ 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? $\endgroup$ – yaodao vang Jan 12 '18 at 19:09
  • $\begingroup$ $$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}$$ $\endgroup$ – yaodao vang Jan 12 '18 at 19:20
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes ,thanks Tobias. Your answer very helpful. $\endgroup$ – yaodao vang Jan 13 '18 at 16:24
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.