Suppose $A \in \mathbb{R}^{m \times n}, x \in \mathbb{R}^n$ and I have the cone $K = \{ x \in R^n : Ax ≥ 0 \}$.

If I am viewing the inequality as an intersection of the halfspaces $a^T_ix ≥ 0, \forall i \in \{1, ..., n \}$ then $a^T_i$ is the normal of a hyperplane and so $A^Ty, y \in R^m$ is a linear combination of the normals of each hyperplane.

However, I do not understand the connection between the column vectors of this matrix and the cone defined by the hyperplanes.

Now in general, linear transformations can be viewed as a mapping from some basis to the standard basis.

What is the connection between the column vectors in $A$ and the hyperplanes defined by $A^T$?


1 Answer 1


The "four subspaces theorem" from linear algebra (emphasized by Gilbert Strang) states that $N(A) = \{ x \in \mathbb R^n \mid Ax = 0 \}$ is the orthogonal complement of $R(A^T) = \{ A^T z \mid z \in \mathbb R^m\}$.

Analogously, the "four cones theorem" tells us that the cone $\{ x \in \mathbb R^n \mid Ax \geq 0 \}$ is the polar of the cone $\{ A^T z \mid z \leq 0 \}$.

The "polar" of a cone $K \subset \mathbb R^n$ is the cone $$ K^\circ = \{y \in \mathbb R^n \mid \langle x, y \rangle \leq 0 \text{ for all } x \in \mathbb K \}. $$ A convex cone is like a "one-sided" version of a subspace, and the polar of a convex cone is analogous to the orthogonal complement of a subspace. The analogy is supported by the fact that if $K$ is a closed convex cone then any vector $x \in \mathbb R^n$ can be decomposed uniquely as $x = x_1 + x_2$, where $x_1 \in K$ and $x_2 \in K^\circ$.

The "four cones theorem" is usually called Farkas's lemma, but the name "four cones theorem" emphasizes the nice analogy with the four subspaces theorem.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .