Boyd & Vandenberghe — Describing simplex as a polyhedron

Question

I am studying convex optimization from Boyd & Vandenberghe's book. In page 35, describing the simplex as a polyhedron, ran as

$B \in \boldsymbol{R}^{n\times k}$ ... matrix $B$ has rank $k$. Therefore, there exits a nonsingular matrix $A=(A_1, A_2) \in \boldsymbol{R}^{n \times n}$ such that

$$AB = \begin{bmatrix} A_1 \\ A_2 \end{bmatrix}, \qquad B = \begin{bmatrix} I \\ 0 \end{bmatrix}$$

I cannot understand why $A$ exists and how come this relation has been induced.

Answer 1

Since $B$ has full rank, $A$ can be obtained by doing Gaussian elimination, similar to finding the inverse of a square matrix of full rank.

You could also expand $B$ to a full-rank matrix $C \in \mathbb{R}^{n \times n}$ by adding complementary basis vectors to the columns of $B$. Define $A = C^{-1}$. Then $A$ fulfills the demanded property.

Answer 2

You can see this via EVD. We have $B \in \mathbf{R}^{n \times k}$ that has rank $k < n$. The EVD of $BB^T$ is $B = ADA^T$ where $A$ could be viewed as $$A = \begin{bmatrix} A_1 \\ A_2 \end{bmatrix}$$ with $A_1 \in \mathbf{R}^{k \times n}$ and $A_2 \in \mathbf{R}^{(n-k) \times n}$ and $D$ contains non-zero eigenvalues in the first $k$ diagonal elements (the rest are zero). Note that $A_1B = B$ and $A_2B = 0$.

Answer 3

I was also puzzled by the same thing, but looking at the book it says such that:

$$ A B=\left[\begin{array}{l}{A_{1}} \\ {A_{2}}\end{array}\right] B=\left[\begin{array}{l}{I} \\ {0}\end{array}\right] $$

which is different from the thing written in the question. (basically no comma there) and

$$AB = \left[\begin{array}{l}{I} \\ {0}\end{array}\right]$$ not $B$.