# Computing an almost Vandermonde matrix

I have this determinant which looks like a Vandermonde matrix

$$D=\begin{vmatrix}1& a_1 & \cdots & a_1^{n-2}& a_1^n\\ 1& a_2 & \cdots & a_2^{n-2}& a_2^n\\ \vdots &\vdots & \ddots & \vdots & \vdots\\ 1& a_n & \cdots & a_n^{n-2}& a_n^n \end{vmatrix}$$

Using the software maxima I found that probably $$D$$ has this form

$$D= \prod_{i but I couldn't prove it. Is my conjecture true and how can I prove it?

Hint:

Consider $$D = \begin{vmatrix} 1&x&x^2&\cdots&x^{n-2} & x^{n-1}&x^n\\ 1&a_1&a_1^2&\cdots&a_1^{n-2} & a_1^{n-1}&a_1^n\\ 1&a_2&a_2^2&\cdots&a_2^{n-2} & a_2^{n-1}&a_2^n\\ \vdots\\ 1&a_n&a_n^2&\cdots&a_n^{n-2} & a_n^{n-1}&a_n^n\\ \end{vmatrix}$$

This is a Vandermonde determinant, so you already know how to calculate it. Look for the coefficient of $$x^{n-1}$$. On the other hand develop the determinant using the first row.

In a similar way, you can see the following generalization: $$\begin{vmatrix} 1&a_1&\cdots&a_1^{k-1}&a_1^{k+1}\cdots &a_1^n\\ 1&a_2&\cdots&a_2^{k-1}&a_2^{k+1}\cdots &a_2^n\\ \vdots\\ 1&a_n&\cdots&a_n^{k-1}&a_n^{k+1}\cdots &a_n^n\\ \end{vmatrix} = \sigma_{n-k}(a_1,a_2\cdots,a_n)\prod_{i

(Here $$\sigma_k$$ denotes the $$k$$-th elementary symmetric polynomial)

You formula is correct. My proof is not pretty.

To compute $$D$$, subtract the last row of the matrix from each of the other rows. The $$i^{th}$$ row will now have a factor of $$a_i-a_n$$, for all $$i\le n-1$$. Factor this out. The first column of the new matrix has a $$1$$ at its bottom, and the rest of its entries are zero, so $$D$$ is equal to the determinant of the upper right $$(n-1)\times (n-1)$$ matrix (times the removed factors). This smaller matrix looks like this: the $$(i,j)$$ entry is the sum of all monomials of the form $$a_i^s a_n^t$$ which satisfy $$s+t=j-1$$. The exception is the last column $$j=n-1$$, where instead the monomials satisfy $$s+t=n-1$$.

Rinse and repeat, subtracting the last row of this new matrix from all others, and factoring out $$(a_i-a_{n-1})$$ from each row. The entries will now be a sum of monomials of the form $$a_i^r a_{n-1}^sa_n^t$$, where $$r+s+t=j-1$$, again with the exception of the last column. As you continue this process, you will see the pattern emerging, and can prove it by induction.

By the end, you will have all the removed factors $$(a_i-a_j)$$ times the determinant of a $$1\times 1$$ matrix. Its entry will be the sum of all monomials of the form $$a_1^{m_1}a_2^{m_2}\cdots a_n^{m_n}$$ which satisfy $$m_1+\dots+m_n=1$$. Of course, this is just $$a_1+\dots+a_n$$.

Two proofs:

1. If I flip the order of the columns of your matrix, I obtain the matrix $$$$\begin{pmatrix} a_1^n & a_1^{n-2} & \cdots & a_1 & 1 \\ a_2^n & a_2^{n-2} & \cdots & a_2 & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_n^n & a_n^{n-2} & \cdots & a_n & 1 \end{pmatrix} = \left( \begin{cases} a_i^{n-j}, & \text{if } j > 1; \\ a_i^n, & \text{if } j = 1 \end{cases} \right)_{1\leq i\leq n, \ 1\leq j\leq n} .$$$$ This latter matrix has determinant $$$$\left(a_1 + a_2 + \cdots + a_n\right) \prod_{1\leq i according to Exercise 6.16 in my Notes on the combinatorial fundamentals of algebra, version of 10 January 2019 (where I use the notations $$x_i$$ instead of $$a_i$$). All that remains is to check that the sign that the determinant incurs when I flip the order of the columns is precisely the sign by which $$\prod_{1\leq i differs from $$\prod_{1\leq i. But this is clear: Both signs are the sign of the permutation $$w_0$$ of the set $$\left\{1,2,\ldots,n\right\}$$ that sends each $$k$$ to $$n+1-k$$. (This sign is explicitly given by $$\left(-1\right)^{n\left(n-1\right)/2}$$, but we do not need to know this.)

2. Your claim is the particular case (for $$\mu = \left(1\right)$$) of the "Bi-Alternant Formula" proved in John R. Stembridge, A Concise Proof of the Littlewood-Richardson Rule, Elec. J. Comb. 9 N5. Indeed, if I rename your $$a_1, a_2, \ldots, a_n$$ as $$x_1, x_2, \ldots, x_n$$ and flip the order of the columns of your matrix, then your $$D$$ becomes $$a_{\left(n, n-2, n-3, \ldots, 1, 0\right)} = a_{\left(1\right) + \rho}$$ in Stembridge's notations. Now the "Bi-Alternant Formula" yields that \begin{align} s_{\left(1\right)} = a_{\left(1\right) + \rho} / a_\rho , \end{align} where $$a_\rho = \det\left(\left( x_i^{n-j} \right)_{1\leq i\leq n,\ 1\leq j\leq n}\right) = \prod\limits_{1 \leq i < j \leq n} \left(x_i - x_j\right)$$ is the genuine Vandermonde determinant and where $$s_{\left(1\right)} = x_1 + x_2 + \cdots + x_n$$. Your result follows, again after checking that the signs are right.

Don't be afraid of either of these two references. My notes are long but it's because I flesh out every triviality in full detail. Stembridge's paper looks advanced but is fully self-contained and highly readable; it is a great first introduction to algebraic combinatorics.

This can be shown in the same way as we show the corresponding identity for the Vandermonde determinant.

Let $$Q(a_1, a_2, \dots, a_n)$$ be the determinant of the matrix, as a degree $$\binom n2+1$$ homogeneous polynomial in $$a_1, a_2, \dots, a_n$$. To prove that $$Q(a_1, a_2, \dots, a_n) = (a_1 + a_2 + \dots + a_n)\prod_{i it's enough to check that a single term such as $$a_2 a_3^2 \dotsm a_{n-1}^{n-2} a_n^n$$ has the same coefficient on both sides (easily done), and that $$Q(a_1, a_2, \dots, a_n)$$ is divisible by every factor on the right-hand side.

For the factors of the form $$a_i -a_j$$, this holds because, when we set $$a_i=a_j=t$$, the matrix has two identical rows, so its determinant is $$0$$. If we were computing the Vandermonde determinant, we'd stop there.

To show that $$Q(a_1, a_2, \dots, a_n)$$ is divisible by $$a_1 + a_2 + \dots + a_n$$, choose any $$a_1, a_2, \dots, a_n$$ such that $$a_1 + a_2 + \dots + a_n = 0$$, and let $$P(x) = (x-a_1)(x-a_2)\dotsm (x-a_n)$$. Then the coefficient of $$x^n$$ in $$P(x)$$ is $$1$$ and by one of Vieta's formulas, the coefficient of $$x^{n-1}$$ in $$P(x)$$ is $$0$$. Therefore $$x^n - P(x)$$ is a linear combination of $$1, x, x^2, \dots, x^{n-2}$$ which is equal to $$a_k^n$$ when $$x = a_k$$: it gives us a way to express the $$n^{\text{th}}$$ column of the matrix in terms of the first $$n-1$$. Therefore the columns of the matrix are linearly dependent, so the determinant is $$0$$ whenever $$a_1 + _2 + \dots + a_n = 0$$, and therefore $$Q(a_1, a_2, \dots, a_n)$$ has a factor of $$a_1 + a_2 + \dots + a_n$$.