Boyd & Vandenberghe — Describing simplex as a polyhedron

discrete geometrylinear algebramatricespolyhedrasimplex

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.

Best Answer

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.

Related Question