Maximizing the Nullity of a Symbolic Gram Matrix

Question

I have a symbolic gram matrix, that is, a matrix $AA^T$ with some entries being variables. I would like to find a solution for my variables which maximizes the nullity of this matrix, or equivalently, maximizes the number of eigenvalues which are 0. Initially I thought to simply solve for when the determinant is 0, however if such a solution exists, then it only tells me that the multiplicity of the zero-valued eigenvalues is at least 1. Does anyone have any suggestions of how to do this computation?

Answer 1

I don't know if this is helpful to you, but anyway.

By rank- nullity theorem, we have:

$\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad \quad \operatorname{rank}\, (M) + \operatorname{null}\, (M) =n, $

where $n$ is the number of columns of $M$.

In order to maximize $\operatorname{null}\, (M)=n-1$, we need to have $\operatorname{rank}\,(M) = 1$.

---

Now, if $M = AA^T$, then if $\operatorname{rank}\, (A) = 1$, it follows that $\operatorname{rank}\, (M) = 1$. So, try to create a matrix $A$ with $\operatorname{rank}\, (A) = 1$.

Answer 2

Just one idea: As you surely know the rank and the nullity of a matrix are related through $\mbox{rank}(B)+\mbox{null}(B)=\mbox{dim}(B)=n$ (let me name $B=AA^T$). If the matrix $B$ has a rank $r$, there exists at least one minor (see https://en.wikipedia.org/wiki/Minor_%28linear_algebra%29) $r\times r$ different from zero. Fiting the parameters such that $\mbox{det}[B]=0$ will ensure the existence of at least one eigenvalue equal to zero. Then, you can continue making zero the $(n-1)\times(n-1)$ minors. If you can make all of them equal to zero, then the matrix sill have at least two zero eigenvales. You can continue this iterative procedure.

For demonstrating that all $(n-1)\times(n-1)$ are equal to zero there is a shortcut, based on the study of the adjoint matrix. As it is explained in Is adjoint of singular matrix singular? What would be its rank? you have three posibilities for the rank of the adjoint matrix: $$\mbox{rank}[\mbox{Adj}(B)]=0\quad if\quad\mbox{rank}[B]\le n-2\\ \mbox{rank}[\mbox{Adj}(B)]=1\quad if\quad\mbox{rank}[B]= n-1\\ \mbox{rank}[\mbox{Adj}(B)]=n\quad if\quad\mbox{rank}[B]=n$$