Why is the maximal value attained at the boundary?

Question

Let $A$ be a real matrix. Denote $\|\cdot \|$ the $p=1$ norm (sum of absolutes of the elements).

Let $C$ be all vectors (of compatible size with $A$) whose elements are in the range $[-1,1]$

How to show that $\arg \max(\|Ax \|$) over all vectors $x$ in $C$ is a vector whose elements are all either $1$ or $-1$?

Answer 1

I find the following answer the most intuitive while requiring the least mathematical knowledge.

Say $\mathbf{A}$ is an $m\times n$ matrix.

Replace absolute values with a vector $y$ with entries $1,-1$ such that: $||Ax||_{p=1} = y^T\mathbf{A}x$

$$y^T\mathbf{A}x = \sum_{i=1}^{m}\sum_{j=1}^{n} y_i a_{ij} x_j = \sum_{j=1}^{n}x_j\sum_{i=1}^{m} y_i a_{ij}$$

Therefore, it is clear that all $x_j$ must be either $1$ or $-1$ in order to maximize the expression $\sum_{i=1}^{m} y_i a_{ij}$, or at least reach the same maximum if this expression is $0$.

Answer 2

A convex function on a compact convex set attains its maximum at an extreme point of the set. Not all points where $\|Ax\|$ attains its maximum need be extreme points though: consider $A=0$, or more generally any $A$ with at least one column $0$.