Return to Answer

There is such an $A$ if and only if $M\geq 5$.

To see this, first note that the condition that $A$ be a convex combination of terms $yy^T$ each with trace $a$ is irrelevant. As long as $A$ is positive semidefinite (and symmetric), it can be written as a convex combination of terms $yy^T$. If $A$ has trace $a$ then linearity of trace means we can rescale these outer products to all have trace $a$ and $A$ will be a convex combination of these scaled matrices.

We call a matrix completely positive if it is a convex combination of terms $yy^T$ with $y\geq 0$ elementwise. We call a matrix doubly nonegative if it is symmetric, elementwise nonnegative, and positive semidefinite. Clearly all completely positive matrices are doubly nonnegative, and the above argument reduces your question to whether there exist doubly nonnegative matrices which are not completely positive.

The fact that such matrices do not exist if $M\leq 4$ was I believe originally shown in Diananda's paper "On non-negative forms in real variables some or all of which are nonnegative". Hall showed that they do exist for $M\geq 5$ (referenced in Diananda's paper).

A nice geometric exposition of these results is given by Gray and Wilson "Nonnegative Factorization of Positive Semidefinite Nonnegative Matrices". The idea is to view the matrix $A$ as a Gram matrix. The question is then whether a set of vectors all having nonnegative inner products with each other can be simultaneously rotated into the nonnegative orthant. They give an example family of vectors which cannot, leading to the $M=5$ counterexample \[ A = \begin{bmatrix} 2 & 0 & 0 & 1 & 1\\\ 0 & 2 & 0 & 1 & 1\\\ 0 & 0 & 1 & 1 & 8\\\ 1 & 1 & 1 &11 & 0\\\ 1 & 1 & 8 & 0 & 74 \end{bmatrix}. \]

There is such an $A$ if and only if $M\geq 5$.

To see this, first note that the condition that $A$ be a convex combination of terms $yy^T$ each with trace $a$ is irrelevant. As long as $A$ is positive semidefinite (and symmetric), it can be written as a convex combination of terms $yy^T$. If $A$ has trace $a$ then linearity of trace means we can rescale these outer products to all have trace $a$ and $A$ will be a convex combination of these scaled matrices.

We call a matrix completely positive if it is a convex combination of terms $yy^T$ with $y\geq 0$ elementwise. We call a matrix doubly nonegative if it is symmetric, elementwise nonnegative, and positive semidefinite. Clearly all completely positive matrices are doubly nonnegative, and the above argument reduces your question to whether there exist doubly nonnegative matrices which are not completely positive.

The fact that such matrices do not exist if $M\leq 4$ was I believe originally shown in Diananda's paper "On non-negative forms in real variables some or all of which are nonnegative". Hall showed that they do exist for $M\geq 5$ (referenced in Diananda's paper).

EDIT: As Denis Serre shows in the comments, the $M=5$ "counterexample" quoted below from Gray and Wilson is in fact not a counterexample at all!

A nice geometric exposition of these results is given by Gray and Wilson "Nonnegative Factorization of Positive Semidefinite Nonnegative Matrices". The idea is to view the matrix $A$ as a Gram matrix. The question is then whether a set of vectors all having nonnegative inner products with each other can be simultaneously rotated into the nonnegative orthant. They give an example family of vectors which cannot, leading to the $M=5$ counterexample \[ A = \begin{bmatrix} 2 & 0 & 0 & 1 & 1\\\ 0 & 2 & 0 & 1 & 1\\\ 0 & 0 & 1 & 1 & 8\\\ 1 & 1 & 1 &11 & 0\\\ 1 & 1 & 8 & 0 & 74 \end{bmatrix}. \]

There is such an $A$ if and only if $M\geq 5$.

To see this, first note that the condition that $A$ be a convex combination of terms $yy^T$ each with trace $a$ is irrelevant. As long as $A$ is positive semidefinite (and symmetric), it can be written as a convex combination of terms $yy^T$. If $A$ has trace $a$ then linearity of trace means we can rescale these outer products to all have trace $a$ and $A$ will be a convex combination of these scaled matrices.

We call a matrix completely positive if it is a convex combination of terms $yy^T$ with $y\geq 0$ elementwise. We call a matrix doubly nonegative if it is symmetric, elementwise nonnegative, and positive semidefinite. Clearly all completely positive matrices are doubly nonnegative, and the above argument reduces your question to whether there exist doubly nonnegative matrices which are not completely positive.

The fact that such matrices do not exist if $M\leq 4$ was I believe originally shown in Diananda's paper "On non-negative forms in real variables some or all of which are nonnegative". Horn showed that they do exist for $M\geq 5$ (referenced in Diananda's paper).

A nice geometric exposition of these results is given by Gray and Wilson "Nonnegative Factorization of Positive Semidefinite Nonnegative Matrices". The idea is to view the matrix $A$ as a Gram matrix. The question is then whether a set of vectors all having nonnegative inner products with each other can be simultaneously rotated into the nonnegative orthant. They give an example family of vectors which cannot, leading to the $M=5$ counterexample \[ A = \begin{bmatrix} 2 & 0 & 0 & 1 & 1\\\ 0 & 2 & 0 & 1 & 1\\\ 0 & 0 & 1 & 1 & 8\\\ 1 & 1 & 1 &11 & 0\\\ 1 & 1 & 8 & 0 & 74 \end{bmatrix}. \]

There is such an $A$ if and only if $M\geq 5$.

To see this, first note that the condition that $A$ be a convex combination of terms $yy^T$ each with trace $a$ is irrelevant. As long as $A$ is positive semidefinite (and symmetric), it can be written as a convex combination of terms $yy^T$. If $A$ has trace $a$ then linearity of trace means we can rescale these outer products to all have trace $a$ and $A$ will be a convex combination of these scaled matrices.

We call a matrix completely positive if it is a convex combination of terms $yy^T$ with $y\geq 0$ elementwise. We call a matrix doubly nonegative if it is symmetric, elementwise nonnegative, and positive semidefinite. Clearly all completely positive matrices are doubly nonnegative, and the above argument reduces your question to whether there exist doubly nonnegative matrices which are not completely positive.

The fact that such matrices do not exist if $M\leq 4$ was I believe originally shown in Diananda's paper "On non-negative forms in real variables some or all of which are nonnegative". Hall showed that they do exist for $M\geq 5$ (referenced in Diananda's paper).

A nice geometric exposition of these results is given by Gray and Wilson "Nonnegative Factorization of Positive Semidefinite Nonnegative Matrices". The idea is to view the matrix $A$ as a Gram matrix. The question is then whether a set of vectors all having nonnegative inner products with each other can be simultaneously rotated into the nonnegative orthant. They give an example family of vectors which cannot, leading to the $M=5$ counterexample \[ A = \begin{bmatrix} 2 & 0 & 0 & 1 & 1\\\ 0 & 2 & 0 & 1 & 1\\\ 0 & 0 & 1 & 1 & 8\\\ 1 & 1 & 1 &11 & 0\\\ 1 & 1 & 8 & 0 & 74 \end{bmatrix}. \]

There is such an $A$ if and only if $M\geq 5$.

To see this, first note that the condition that $A$ be a convex combination of terms $yy^T$ each with trace $a$ is irrelevant. As long as $A$ is positive semidefinite (and symmetric), it can be written as a convex combination of terms $yy^T$. If $A$ has trace $a$ then linearity of trace means we can rescale these outer products to all have trace $a$ and $A$ will be a convex combination of these scaled matrices.

We call a matrix completely positive if it is a convex combination of terms $yy^T$ with $y\geq 0$ elementwise. We call a matrix doubly nonegative if it is symmetric, elementwise nonnegative, and positive semidefinite. Clearly all completely positive matrices are doubly nonnegative, and the above argument reduces your question to whether there exist doubly nonnegative matrices which are not completely positive.

The fact that such matrices do not exist if $M\leq 4$ was I believe originally shown in Diananda's paper "On non-negative forms in real variables some or all of which are nonnegative". Horn showed that they do exist for $M\geq 5$ (referenced in Diananda's paper). A nice geometric exposition of these results is given by Gray and Wilson "Nonnegative Factorization of Positive Semidefinite Nonnegative Matrices". As an example of such a matrix for $M=5$ they give \[ A = \begin{bmatrix} 2 & 0 & 0 & 1 & 1\\\ 0 & 2 & 0 & 1 & 1\\\ 0 & 0 & 1 & 1 & 8\\\ 1 & 1 & 1 &11 & 0\\\ 1 & 1 & 8 & 0 & 74 \end{bmatrix}. \]

There is such an $A$ if and only if $M\geq 5$.

To see this, first note that the condition that $A$ be a convex combination of terms $yy^T$ each with trace $a$ is irrelevant. As long as $A$ is positive semidefinite (and symmetric), it can be written as a convex combination of terms $yy^T$. If $A$ has trace $a$ then linearity of trace means we can rescale these outer products to all have trace $a$ and $A$ will be a convex combination of these scaled matrices.

We call a matrix completely positive if it is a convex combination of terms $yy^T$ with $y\geq 0$ elementwise. We call a matrix doubly nonegative if it is symmetric, elementwise nonnegative, and positive semidefinite. Clearly all completely positive matrices are doubly nonnegative, and the above argument reduces your question to whether there exist doubly nonnegative matrices which are not completely positive.

The fact that such matrices do not exist if $M\leq 4$ was I believe originally shown in Diananda's paper "On non-negative forms in real variables some or all of which are nonnegative". Horn showed that they do exist for $M\geq 5$ (referenced in Diananda's paper).

A nice geometric exposition of these results is given by Gray and Wilson "Nonnegative Factorization of Positive Semidefinite Nonnegative Matrices". The idea is to view the matrix $A$ as a Gram matrix. The question is then whether a set of vectors all having nonnegative inner products with each other can be simultaneously rotated into the nonnegative orthant. They give an example family of vectors which cannot, leading to the $M=5$ counterexample \[ A = \begin{bmatrix} 2 & 0 & 0 & 1 & 1\\\ 0 & 2 & 0 & 1 & 1\\\ 0 & 0 & 1 & 1 & 8\\\ 1 & 1 & 1 &11 & 0\\\ 1 & 1 & 8 & 0 & 74 \end{bmatrix}. \]