3
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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