# Linear Algebra of Symmetric Sums: a converse question

An on-going effort to answer this question has brought up various other questions. Most recently, I have been wondering: given a set of $n$ distinct non-zero complex numbers, $z_1, \dots, z_j, \dots , z_n$, and given the values of the first $n+1$ the power sums, $\mathcal{Z}_0, \mathcal{Z}_1, \dots, \mathcal{Z}_n$: $$\begin{bmatrix} 1 & 1 & \cdots & 1 \\ z_{1} & z_{2} & \cdots & z_{n} \\ z_{1}^{2} & z_{2}^2 & \cdots & z_{n}^{2} \\ \vdots & \vdots & \ddots & \vdots \\ z_{1}^n & z_{2}^n & \cdots & z_{n}^n \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix} = \begin{bmatrix} \mathcal{Z}_0 \\ \mathcal{Z}_1 \\ \mathcal{Z}_2 \\ \vdots \\ \mathcal{Z}_n \end{bmatrix}$$

from the Linear Algebra of Symmetric Sums question, we know that these $n$ equations (if you don't include $\mathcal{Z}_0 = n$) determine the $z_j$'s. What if we consider the converse? How does requiring the $z_j$'s to be non-zero and distinct restrict the possible values for the power sums, the $\mathcal{Z}_k$'s? Clearly, they cannot all be zero, but there must be a large number of other choices for $\mathcal{Z}_1, \dots, \mathcal{Z}_n$ that produce non-distinct or zero values for some of the $z_j$'s.

Note

This may appear to ask two different questions:

1. What is the effect of requiring the $z_j$'s to be non-zero?

2. What is the effect of requiring them to be distinct?

But a $z_j$ that is zero or two, say $z_j$ and $z_l$, that are the same have a very similar effect on the power sum equations: they shrink the problem from a problem with $n$ independent equations to one with $n-1$ (or fewer) independent equations and an extra dependent equation or two.

In fact, considering this question in this fashion, I may have a sort of answer, albeit a horrendously ugly answer. Consider each of the myriad, but finite number of, ways the $z_j$'s can be degenerate: one $z_j$ zero, two of them zero, one zero and two not distinct, etc., and with that as an assumption, using the technique of the second half of this answer, attempt to calculate the dependent $\mathcal{Z}_k$ equations from the others. If it works, the present set of $\mathcal{Z}_k$'s is degenerate.

Anyway, I am looking for a more tractable answer which might allow me to look at some sets of values for the $\mathcal{Z}_k$'s (especially sets with lots of zeros) and recognize them as not possible.

A Reformulation of the Question

Given the discussion in the note, or given Arturo's determinant calculation in his comment, we can reformulate the question equivalently as:

Given a set of any $n$ complex numbers, $z_1, \dots , z_n$, and given the values of the first $n+1$ the power sums, $\mathcal{Z}_0, \mathcal{Z}_1, \dots, \mathcal{Z}_n$:

$$\mathcal{Z}_0 =n$$ $$\begin{bmatrix} z_{1} & z_{2} & \cdots & z_{n} \\ z_{1}^{2} & z_{2}^2 & \cdots & z_{n}^{2} \\ \vdots & \vdots & \ddots & \vdots \\ z_{1}^n & z_{2}^n & \cdots & z_{n}^n \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix} = \begin{bmatrix} \mathcal{Z}_1 \\ \mathcal{Z}_2 \\ \vdots \\ \mathcal{Z}_n \end{bmatrix} ,$$ can you use the values of the power sums to determine whether the matrix is singular or not?

-
Dropping the first row, then, you get a Vandermonde matrix multiplies by $z_1\cdots z_n$. The determinant will then be equal to$$z_1\cdots z_n\prod_{1\leq i\lt j\leq n}(z_j-z_i).$$If the $z_i$ are nonzero and pairwise distinct, then the remaining matrix has nonzero determinant, so the system $M\mathbf{x}=\mathbf{b}$ always has a unique solution. So choosing either the $\mathcal{Z}_i$ or the vector $\mathbf{x}$ completely determines everything. If either not all $z_i$ are nonzero, or $z_i=z_j$ for $i\neq j$, the system may or may not have a solution, and solutions may not be unique. –  Arturo Magidin Mar 11 '11 at 22:34
My question is: given only the $\mathcal{Z_k}$'s and that $x=(1,1, \dots, 1)$ can I tell if the matrix $M$ is singular or not? –  Eric Nitardy Mar 12 '11 at 1:29

In a comment you say that you want to know whether from knowing the values of the power sum symmetric polynomials on $z_1,\ldots,z_n$ you can determine whether the $z_i$ are pairwise distinct and nonzero, or not.

The power sum symmetric polynomials \begin{align*} p_1(z_1,\ldots,z_n) &= z_1+\cdots + z_n\\ p_2(z_1,\ldots,z_n) &= z_1^2 + \cdots + z_n^2\\ &\vdots\\ p_n(z_1,\ldots,z_n) &= z_1^n + \cdots + z_n^n \end{align*} generate the ring of symmetric polynomials over $\mathbb{Q}$.

In particular, you can express the elementary symmetric polynomials in $z_1,\ldots,z_n$ as sums of rational multiples of products of the power sum symmtric polynomials. So you can express \begin{align*} e_1(z_1,\ldots,z_n) &= z_1+\cdots + z_n\\ e_2(z_1,\ldots,z_n) &= z_1z_2 + z_1z_3+\cdots+z_1z_n+z_2z_3+\cdots+z_{n-1}z_n\\ &\vdots\\ e_n(z_1,\ldots,z_n) &= z_1\cdots z_n \end{align*} in terms of $p_1,\ldots,p_n$.

Plugging in the values $\mathcal{Z}_1,\ldots,\mathcal{Z}_n$ that you know for $p_1,\ldots,p_n$, that would determine the values of $e_1,\ldots,e_n$. With the values of $e_1,\ldots,e_n$, you get the coefficients of $$(x-z_1)(x-z_2)\cdots(x-z_n)$$ because the coefficients are precisely the elementary symmetric polynomials in $z_1,\ldots,z_n$.

But it is a trivial matter to determine if this polynomial has zero as a root, or if it has repeated roots (for the latter, check the gcd with the derivative). Thus, from the values of $p_1,\ldots,p_n$ you can determine if the $z_i$ are pairwise distinct and nonzero, or not, which in turn tells you if $M$ is nonsingular or not.

In summary: yes, you can tell if $M$ is singular or nonsingular, by computing the polynomial $(x-z_1)\cdots(x-z_n)$ via symmetric polynomials.

How does this relate to the question in the first paragraph, though?

First: if you write the symmetric polynomial $z_1\cdots z_n$ in terms of the power symmetric polynomials, then setting this equal to $0$ gives you a polynomial with rational coefficients in $\mathcal{Z}_1,\ldots,\mathcal{Z}_n$. The $z_i$ are nonzero if and only if the $\mathcal{Z}_i$ do not satisfy this polynomial. This gives you precisely the locus of vectors $(\mathcal{Z}_1,\ldots,\mathcal{Z}_n)^T$ that are excluded by the condition "all $z_i$ are nonzero."

For example: take the case $n=2$. Then we express $z_1z_2$ in terms of $z_1+z_2$ and $z_1^2 + z_2^2$: $$z_1z_2 = \frac{1}{2}\left( (z_1+z_2)^2 - (z_1^2+z_2^2)\right) = \frac{1}{2}(\mathcal{Z}_1^2 - \mathcal{Z}_2).$$ Therefore, one of $z_1$ and $z_2$ is zero if and only if $\mathcal{Z}_1^2 - \mathcal{Z}_2 = 0$.

Therefore, the vectors $(\mathcal{Z}_1,\mathcal{Z}_2)$ that are excluded by the condition "$z_1$ and $z_2$ are both nozero" are exactly the points that lie on the grap of $y=x^2$.

This is fairly straightforward to do in any value of $n$, once you express $z_1\cdots z_n$ in terms of the power sum symmetric polynomials. So certainly, it is easy to write down a polynomial expression that determines exactly the locus of all "bad $(\mathcal{Z}_1,\ldots,\mathcal{Z}_n)$" that lead to at least one $z_i$ equal to $0$.

Added, Edited. (This is what I get for posting at 1am. I forget things like "discriminant" and "resultant.")

To determine if the polynomial has repeated roots, you can just look at the discriminant. The discriminant is a function of the coefficients of $(x-z_1)\cdots(x-z)n)$, and since we can compute the coefficients using the $\mathcal{Z}_i$, then we can compute the discriminant. It will be a polynomial in the coefficient, hence a polynomial in the $\mathcal{Z}_i$.

The key is that the discriminant is also equal to the product $\displaystyle\prod_{1\leq i\lt j\leq n}(z_i - z_j)^2$, and therefore the discriminant is equal to $0$ if and only if the polynomial has repeated roots. (In the $n=2$ case, what I was looking at, $\frac{1}{2}\mathcal{Z}_1^2 =\mathcal{Z}_2$, was just the discriminant of the quadratic polynomial, but with my algebra error and the hour, I failed to notice).

So: setting the discriminant equal to $0$ gives you the condition for repeated roots, and setting the constant term equal to $0$ gives you the condition for a root to be zero. The two together determine two varieties in affine $n$-space, and the locus of "bad tuples" is precisely their union.

In short: yes, you can determine exactly which $(\mathcal{Z}_1,\ldots,\mathcal{Z}_n)$ correspond to singular matrices and which to nonsingular matrices; it is described as the union of two affine varieties in $\mathbb{C}^n$, which can be written as two polynomials (with rational coefficients) in the $\mathcal{Z}_i$.

-
Thank you for your answer. I think that you have resolved the "some of $z_j$'s are zero" issue. There is an algebra error in your $n=2$ non-distinct discussion. The criteria should be $$\frac{1}{2}\mathcal{Z_1}^2=\mathcal{Z_2}.$$ –  Eric Nitardy Mar 12 '11 at 15:14
@Eric: I think you're right. Thanks. –  Arturo Magidin Mar 12 '11 at 20:15
@Eric: You know what? On reflection it's not that bad. You can just use the discriminant of the polynomial. I'll write this up later, and I think it will be pretty easy. –  Arturo Magidin Mar 12 '11 at 20:18
I found a straightforward way to calculate the constant term from the from the powers sums, but I have not found a good way to calculate the discriminant from the power sums. Is the only way to calculate the all the coefficients of the polynomial and then find the determinant of the Sylvester matrix? –  Eric Nitardy Mar 13 '11 at 0:31
@Eric: Honestly, I don't know. It's not something I've ever looked into. –  Arturo Magidin Mar 13 '11 at 0:45