# Convex hull of idempotent matrices

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

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\}$

• At the very least, we know that every matrix in the hull has a trace between $0$ and $n$. For all I know, we might get every matrix with trace between $0$ and $n$. – Omnomnomnom Oct 9 '15 at 18:34
• A condition on trace seems quite loose, however. Is there a smaller convex set containing the idempotent matrices? – Justin Solomon Oct 9 '15 at 18:42
• I really don't know. By the way, it looks like your question is about to be closed because it "needs more context". – Omnomnomnom Oct 9 '15 at 18:46
• I think the problem that people may have is that it looks like you didn't put enough work into answering the question yourself. – Omnomnomnom Oct 9 '15 at 18:52
• Sure, but the people of the site and the powers that be tend to expect some kind of partial work, though not necessarily a partial result. I happen to think your question is fine as is. – Omnomnomnom Oct 9 '15 at 18:55

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

• so do we know that there won't be any matrices with trace $2$ besides $I$? – Omnomnomnom Oct 9 '15 at 19:14
• Also, what about matrices with trace $0$? – Omnomnomnom Oct 9 '15 at 19:17
• An idempotent matrix of trace $k$ is a projection on a subspace of dimension $k$. The only subspace of dimension $2$ is the whole space, and a projection on that is the identity. The only subspace of dimension $0$ is $\{0\}$, and a projection on that is $0$. – Robert Israel Oct 9 '15 at 19:25
• I see, there is a unique idempotent element with trace $2$ (or $0$), and so the convex hull must also have a unique such element. – Omnomnomnom Oct 9 '15 at 19:32
• Wow! Thanks to both of you for your help -- it's much appreciated. I'm surprised the convex hull is so big. – Justin Solomon Oct 9 '15 at 19:50

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