# Linear decomposition of positive semi-definite matrices

It is true that the vector space of $n\times n$ Hermitian matrices is an $n^2-$dimensional real vector space and that one can find a basis for this space consisting exclusively of positive semi-definite matrices (see basis for hermitian matrices). My question is, if we have the linear combination $$M=\sum_{k=1}^{n^2}x_kB_k$$ where $B_k$ is the aforementioned positive semi definite basis matrix, what are the restrictions on $x_k$ so that $M$ remains positive semi-definite? A sufficient condition is (I think) that all $x_k\geq 0$, but I don't think it is necessary. If $B_k$ were real numbers, the solution to that problem would be one of the two halfspaces into which $\mathbb{R}^{n^2}$ is divided into by the hyperplane $\sum_{k=1}^{n^2}x_kB_k=0$. Could there be an analogy with this case, when $B_k$ belong to the vector space of Hermitian matrices?

• I think it is possible to choose $B_k$ such that the condition $x_k \geq 0$ is necessary. However, in general, the exact conditions will depend on the choice of basis. – Omnomnomnom May 13 '15 at 13:02
• @AlgebraicPavel is it possible to select such a basis? – Omnomnomnom May 13 '15 at 14:17
• @AlgebraicPavel Are you sure about the dimension? One has to select $n$ real diagonal elements, and $n(n-1)/2$ complex elements, which adds up to $n^2$ real parameters. BTW, I am using as a basis the construction of math.stackexchange.com/questions/150643/… , therefore the condition $B_iB_j=0$ is not fulfilled automatically. – Bryson of Heraclea May 13 '15 at 14:22
• @Omnomnomnom Good point. It does not exist unless $n=1$ (the trivial case). There are at most $n$ nonzero HPSD matrices with this property and, well, $n<n^2$ otherwise :-) – Algebraic Pavel May 13 '15 at 14:55
• @BrysonofHeraclea No I'm not, that's why I removed the comment. – Algebraic Pavel May 13 '15 at 14:55

Thm: Let $B_i\in M_n$ be a positive semidefinite Hermitian matrix for $1\leq i\leq s$. If $\sum_{i=1}^sa_iB_i$ is positive semidefinite iff $a_i\geq 0$ then $s\leq n$.
Proof: If $\Im(B_2)\subset\Im(B_1)$ then there is a small $a_2>0$ such that $B_1-a_2B_2$ is positive semidefinite. Thus, $\Im(B_2)$ is not a a subset of $\Im(B_1)$ and $rank(B_1+B_2)>rank(B_1)$. If $\Im(B_3)\subset\Im(B_1+B_2)$, then there is a small $a_3>0$ such that $B_1+B_2-a_3B_3$ is positive semidefinite. Thus, $\Im(B_3)$ is not a a subset of $\Im(B_1+B_2)$and $rank(B_1+B_2+B_3)>rank(B_1+B_2)$. We can repeat the argument $s$ times and if $s>n$ then $rank(B_1+\ldots+B_{n+1})>n$, which is impossible. So $s\leq n$.
• Thank you very much for the reply! This is a significant step towards the more general answer. By $\mathfrak{I}(B_i)$ do you mean the range (columnspace) of the matrix $B_i$ ? – Bryson of Heraclea May 18 '15 at 7:27
• Hi @BrysonofHeraclea. Yes you are right, $\Im(B_i)$ is the column space. – Daniel May 18 '15 at 12:46