¿Por qué el$BB^T$ siempre es invertible?

Question

En Karmarkar del método, se utiliza $$[I - B^T(BB^T)^{-1}B]v$$ Why does $BB^T$ siempre tiene un inverso?

---

Karmarkar el método se aplica a un LP en el siguiente formulario:

$\min z = cx$

sujeto a

$AX=0$

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

$X\ge0$

$x =[x_1 ,x_2,.....,x_n]^T$, $A$ es una $m \times n$ matriz, $c = [c_1, c_2, ..... ,c_n]$ ,y 0 es un n-dimensional vector columna de ceros. El LP también debe satisfacer $[\frac{1}{n},\frac{1}{n},.....,\frac{1}{n}]^T$ es factible , Óptimo $z-$$=0$

B es el $(m * 1) * n$ matriz cuya primera m filas de a y cuya última fila es un vector de $1'$s.

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

Answer 1

La declaración no es verdadera.

Por ejemplo, si$A= \begin{bmatrix} 2& 3\\1 & 1 \end{bmatrix}$, luego$det(BB^T)=0$ so$BB^T$ no es invertible.

Answer 2

Para una matriz general $B$ esta afirmación no es verdadera, véase el ejemplo de arriba. Pero para el algoritmo de Karmarkar o método de punto interior que se especifica el $B$.

Si usted quiere resolver el siguiente LP $min \ c^Tx \quad s.t. Ax = 0, e^Tx = n, x \geq 0$ donde $x \in \mathbb{R}^n, A \in \mathbb{R}^{m \times n}$ con $n>2, m<n$, $e = (1,...,1)^T \in \mathbb{R}^n$ y con $ rank A = m, Ae = 0$. Deje $\bar{x}$ ser un posible punto, a continuación, definimos $D = diag(\bar{x})$. La matriz $B$ está definido por $$B = \begin{pmatrix} AD \\ e^T\end{pmatrix} \in \mathbb{R}^{(m+1) \times n}$$ Por lo tanto $$BB^T \in \mathbb{R}^{(m+1)\times (m+1)}$$ A continuación, usted sólo tiene que demostrar que $$rank (B) = m+1$$ since $rango(A) = rango(AA^T)$

Para mostrar esto nos fijamos en el núcleo de $B$ y muestran el kernel solo es el vector cero. Vamos $$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 $rango(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$ siempre ha inversa en virtud de las limitaciones anteriores.