0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Omnomnomnom Oct 9 '15 at 18:34
  • $\begingroup$ A condition on trace seems quite loose, however. Is there a smaller convex set containing the idempotent matrices? $\endgroup$ – Justin Solomon Oct 9 '15 at 18:42
  • 1
    $\begingroup$ I really don't know. By the way, it looks like your question is about to be closed because it "needs more context". $\endgroup$ – Omnomnomnom Oct 9 '15 at 18:46
  • 1
    $\begingroup$ I think the problem that people may have is that it looks like you didn't put enough work into answering the question yourself. $\endgroup$ – Omnomnomnom Oct 9 '15 at 18:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Omnomnomnom Oct 9 '15 at 18:55
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ so do we know that there won't be any matrices with trace $2$ besides $I$? $\endgroup$ – Omnomnomnom Oct 9 '15 at 19:14
  • $\begingroup$ Also, what about matrices with trace $0$? $\endgroup$ – Omnomnomnom Oct 9 '15 at 19:17
  • $\begingroup$ 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$. $\endgroup$ – Robert Israel Oct 9 '15 at 19:25
  • $\begingroup$ 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. $\endgroup$ – Omnomnomnom Oct 9 '15 at 19:32
  • $\begingroup$ Wow! Thanks to both of you for your help -- it's much appreciated. I'm surprised the convex hull is so big. $\endgroup$ – Justin Solomon Oct 9 '15 at 19:50
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.