Convex hull of idempotent matrices

Question

What is the convex hull of the set of $n\times n$ (potentially asymmetric) idempotent matrices?

Apparently the powers that be want more information:

Consider the set $S:=\{A\in\mathbb{R}^{n\times n}:A^2=A\}$, the set of idempotent matrices. Is there a simple description of the convex hull of $S$?

By convex hull, I mean: $C:=\{\sum_i a_i M_i:\sum_ia_i=1,a_i\geq0,M_i\in S\}$

Answer 1

First I'll do the $2 \times 2$ case. Consider a $2 \times 2$ matrix of trace $1$:
$$ A = \pmatrix{a & b\cr c & 1-a\cr}$$ For any real $r$, every point $(b,c)$ in the plane is a convex combination of two points on the hyperbola $x y = -r$ (the two axes in the case $r=0$). Thus $A$ is a convex combination of two idempotent matrices of the form $$ \pmatrix{ a & x\cr y & 1-a\cr}$$ where $xy = a-a^2$. The only idempotent matrix of trace $0$ is $0$, and the only idempotent matrix of trace $2$ is $I$. Any matrix of trace strictly between $0$ and $1$ is a convex combination of $0$ and a matrix of trace $1$, while any matrix of trace strictly between $1$ and $2$ is a convex combination of $I$ and a matrix of trace $1$. Thus the convex hull in the $2 \times 2$ case consists of $0$, $I$ and all $A$ with $0 < \text{tr}(A) < 2$.

This leads to a solution in the $n \times n$ case for any $n > 2$. We have idempotent matrices of trace $1$ with the form $$\pmatrix{a & x & 0 & \ldots & 0\cr y & 1-a & 0 & \ldots & 0\cr 0 & 0 & 0 & \ldots & 0\cr \ldots & \ldots & \ldots & \ldots & \ldots\cr 0 & 0 & 0 & \ldots & 0\cr}$$ where $xy = a - a^2$, and convex combinations of these give all $n \times n$ matrices of trace $1$ that are $0$ outside the top left $2 \times 2$ submatrix. By permuting indices, we get all $n \times n$ matrices of trace $1$ that are $0$ outside some principal $2 \times 2$ submatrix. Convex combinations of these give us all $n \times n$ matrices of trace $1$. Now any $n \times n$ matrix of trace strictly between $0$ and $1$ is a convex combination of $0$ and a matrix of trace $1$, while any matrix of trace strictly between $1$ and $n$ is a convex combination of $I$ and a matrix of trace $1$. Thus we find that the convex hull consists of $0$, $I$ and all $A$ with $0 < \text{tr}(A) < n$.

Answer 2

The result can be generalized by induction. Let $C_n$ denote the convex hull over $n \times n$ matrices.

First of all, note that if $A \in C_{n-1}$ and $x \in \Bbb R^n$, then the elements $$ \pmatrix{A&0\\0&0_{1\times 1}},E_x := \pmatrix{I_{n-1}&x\\0&0} $$ are all in $C_n$.

Next, note that $C_n$ is closed under similarity (anything similar to an element of $C_n$ is in $C_n$).

Now, take any upper triangular $A \in C_{n-1}$. That is, $$ A = \pmatrix{\lambda_1 & * \cdots \\ &\ddots\\ && \lambda_{n-1}} $$ with $\sum\lambda_i \in (0,n-1)$. Note that any convex combination of $A$ and $I$ is in $C_n$. Also, any convex combination of a matrix $C_n$ with $E_x$ is in $C_n$.

Conclude that $C_n$ contains every upper triangular matrix with trace (strictly) between $0$ and $n$ and a non-negative bottom-right entry. Because every matrix is upper-triangularizable, conclude that $C_n$ contains every matrix with trace strictly between $0$ and $n$.