# Prove that matrices of this form have eigenvalues $0,1,\ldots , n-1$

Fix arbitrary real numbers $$x_1,\ldots ,x_n$$ which are pairwise distinct, i.e. so that $$x_i \neq x_j$$ for any pair $$i \neq j$$. Let $$A = (a_{ij})$$ be the following $$n \times n$$ matrix: Its diagonal entries are given by the equation,

$$a_{ii}=\sum_{j\neq i}\frac{x_i}{x_i-x_j},$$

while its off-diagonal entries given by the equation,

$$a_{ij}=\frac{x_i}{x_i-x_j}$$,

for $$i\neq j$$. For instance when n=2, the matrix looks like:

$$A=\begin{pmatrix} \frac{x_1}{x_1-x_2} & \frac{x_1}{x_1-x_2}\\ \frac{x_2}{x_2-x_1} & \frac{x_2}{x_2-x_1} \end{pmatrix}$$

Prove that the set of eigenvalues for the matrix A is of the form $$\left \{0,1,\ldots,n-1\right \}$$.

I'm completely lost as to how to continue. I've tried to work on the determinant of $$A-\lambda I$$ for $$2 \times 2$$ and $$3 \times 3$$ matrices $$A$$ but I haven't managed to find anything helpful towards the proof.

Update 1

I'm not entirely sure how to write this formula nicely as a mathematical expression, but as code in python I have that the $$k$$th element of $$v_0$$ is

        p = product([L[i-1] - L[j-1] for i in [1..n] for j in [i+1..n] if i != k and j != k])
v[k-1] = p if k % 2 == 1 else -p


where L refers to the list [x_1,...,x_n], and I want for $$1 \leq i < j \leq n$$ and for $$i \neq j \neq k$$

I also have that $$v_i$$ is equal to $$diag(x_1,...,x_n)^{i}v_0$$

Update 2

the eigenvectors for the case where $$n=4$$ are, $$v_0 = \begin{pmatrix} 1\\ -\frac{x_1^2 - x_1x_3 - (x_1 - x_3)x_4}{x_2^2 - x_2x_3 - (x_2 - x_3)x_4}\\ \frac{x_1^2 - x_1x_2 - (x_1 - x_2)x_4}{x_2x_3 - x_3^2 - (x_2 - x_3)x_4}\\ -\frac{x_1^2 - x_1x_2 - (x_1 - x_2)x_3}{x_2x_3 - (x_2 + x_3)x_4 + x_4^2} \end{pmatrix},$$

$$v_1 = \begin{pmatrix} 1\\ -\frac{x_1^2x_2 - x_1x_2x_3 - (x_1x_2 - x_2x_3)*x_4}{x_1x_2^2 - x_1x_2x_3 - (x_1x_2 - x_1x_3)x_4}\\ -\frac{(x_1 - x_2)x_3x_4 - (x_1^2 - x_1x_2)x_3}{x_1x_2x_3 - x_1x_3^2 - (x_1x_2 - x_1x_3)x_4}\\ -\frac{(x_1^2 - x_1x_2 - (x_1 - x_2)x_3)x_4}{x_1x_2x_3 + x_1x_4^2 - (x_1x_2 + x_1x_3)x_4} \end{pmatrix},$$

$$v_2 = \begin{pmatrix} 1\\ -\frac{x_1^2x_2^2 - x_1x_2^2x_3 - (x_1x_2^2 - x_2^2x_3)x_4}{x_1^2x_2^2 - x_1^2x_2x_3 - (x_1^2x_2 - x_1^2x_3)x_4}\\ -\frac{(x_1 - x_2)x_3^2x_4 - (x_1^2 - x_1x_2)x_3^2}{x_1^2x_2x_3 - x_1^2x_3^2 - (x_1^2x_2 - x_1^2x_3)x_4}\\ -\frac{x_1^2 - x_1x_2 - (x_1 - x_2)x_3)x_4^2}{x_1^2x_2x_3 + x_1^2x_4^2 - (x_1^2x_2 + x_1^2x_3)x_4} \end{pmatrix},$$

$$v_3 = \begin{pmatrix} 1\\ -\frac{x_1^2x_2^3 - x_1x_2^3x_3 - (x_1x_2^3 - x_2^3x_3)x_4}{x_1^3x_2^2 - x_1^3x_2x_3 - (x_1^3x_2 - x_1^3x_3)x_4}\\ -\frac{(x_1 - x_2)x_3^3x_4 - (x_1^2 - x_1x_2)x_3^3}{x_1^3x_2x_3 - x_1^3x_3^2 - (x_1^3x_2 - x_1^3x_3)x_4}\\ -\frac{x_1^2 - x_1x_2 - (x_1 - x_2)x_3)x_4^3}{x_1^3x_2x_3 + x_1^3x_4^2 - (x_1^3x_2 + x_1^3x_3)x_4} \end{pmatrix}$$

Update 3

I managed to work out a formula for the $$j$$th element of the eigenvector with $$eigenvalue=\lambda$$ and $$size=n$$,

$$(-1)^{j+1}\frac{x_j^\lambda}{x_1^\lambda} \prod_{k\neq 1,k\neq j}^n \frac{x_1-x_k}{x_j-x_k}$$

I'm just not sure now as to how to use the formula for one entry of an eigenvector to prove the set of eigenvalues

• If you multiply $A$ by a constant, the eigenvalues get multiplied by the same constant. In your 2D case it looks useful to multiply by $x_2-x_1$. For the 3D case multiply by the product of the three differences between the $x_i$ Oct 15 '20 at 2:30
• @RossMillikan I have already tried that and I got that for the $4 \times 4$ for example that multiplying the eigenvector associated with the $\lambda = 0$ with $(x_2-x_3)(x_2-x_4)(x_3-x_4)$, we get a nicer form of $$v_0=\begin{pmatrix} (x_2-x_3)(x_2-x_4)(x_3-x_4)\\ -(x_1-x_3)(x_1-x_4)(x_3-x_4)\\ (x_1-x_2)(x_1-x_4)(x_2-x_4)\\ -(x_1-x_2)(x_1-x_3)(x_2-x_3)\\ \end{pmatrix}$$ Oct 15 '20 at 2:41
• and multiplying by the matrix $diag(x_1,x_2,x_3,x_n)$ gives us $v_1$ and so on, but I'm unable to give a proper proof or formulate a proper line of reason for a general case Oct 15 '20 at 2:42
• Can you list out the vectors explicitly for $n=4$? Oct 15 '20 at 13:15

For $$k = 0, 1, \ldots, n-1$$, consider the (horizontal) vector $$v_k$$ with $$i$$th coordinate $$\sum \prod_{j=1, a_j \neq i}^{k} {x_{a_j}}.$$

For example, with $$n = 3$$, we have
$$v_0 = (1, 1, 1)$$,
$$v_1 = (x_2 + x_3, x_3 + x_1, x_1 + x_2)$$,
$$v_2 = ( x_2x_3, x_3x_1, x_1x_2)$$.

With $$n = 4$$, we have
$$v_0 = (1, 1, 1, 1)$$,
$$v_1 = (x_2 + x_3 + x_4, x_3 + x_4 + x_1, x_4 + x_1 + x_2, x_1 + x_2 + x_3)$$,
$$v_2 = ( x_2x_3+x_3x_4+x_4x_2, x_3x_4+x_4x_1+x_1x_3, x_4x_1+x_1x_2+x_2x_4, x_1x_2 + x_2x_3 + x_3x_2)$$,
$$v_3 = (x_2x_3x_4, x_3x_4x_1, x_4x_1x_2, x_1x_2x_3)$$.

Claim: $$v_kA = (n-1-k) v_k$$.

Proof: Expand it. A lot of the cross terms cancel out.
For example, with $$v_0$$, the column sum is $$n-1$$, so $$v_0 A = (n-1) v_0$$.
For example, with $$v_{k-1}$$, the numerators are all $$\prod x_i$$, and by looking at the denomninators, they cancel out to 0, so $$v_{k-1} A = 0$$.

Do you see how we get $$v_k A = (n-1-k)v_k$$?

Corollary: The eigenvalues are $$0, 1, 2, \ldots, n-1$$.

• Could this problem be explained/solved using right eigenvectors instead? Oct 15 '20 at 3:17
• @panzershreks I couldn't come up with a nice classification for the right eigenvectors for general $n$, though $n=2, 3$ had a simple expression. $v_k$ has $i$th coordinate $x_i ^{k} (x_i - x_{i+1} )$. This failed for $n=4$, because the denominator got in the way. Because the $i$th row is a multiple of $x_i$, it makes it slightly harder to give us the $A v_k = \lambda v_k$. Oct 15 '20 at 4:01
• It was generated by looking at small $n = 2, 3$ and realizing that's the pattern. I then tested $n=4$ and it works. Oct 15 '20 at 4:04
• I can't make sense of what you're saying. What is $L[i-1]$? What is the product indexed over? You want $1 \leq i < j \leq n$? Oct 15 '20 at 4:16
• I replied to your question in an edit to my post. I'm specifically trying to look for a solution in terms of right eigenvectors as this was an exercise in python to compute the A and it's eigenvectors for up to a $5 \times 5$ matrix and to use the computed result to prove the conjecture. I'm asked to prove the conjecture "by exhibiting a complete set of eigenvalues and eigenvectors for the matrix A (of arbitrary size)" Oct 15 '20 at 4:24

Another possibility, though not nearly as good as the answer just given by Calvin Lin, may be, if nothing else immediately came to mind, start of with sort of a constructive proof beginning with substituting one of the eigenvalues, 0 thru n-1, into $$A-\lambda I$$ and then by the usual gauss elimination by rows with row swaps(interchanges) if necessary, as one would use in solving a linear system how one will always end up with the last row(s) being all zeros meaning that from the row just prior one or more of the pertinent quantities can be chosen arbitrarily. Which essentially means there is dependency in that not all of the rows are independent - again i mean in the system $$A-\lambda I$$ where $$\lambda$$ is chosen one of the integers 0 thru n-1. One may also start off with low ordered matrices and then by induction show the same result of last row being all zeros. Anyway after examining this procedure one may be able to deduce a better explanation such as that just given by Lin or similar. By the way did Lin not make a slight error in that for n=4 the first or highest eigenvector $$v_0$$ should be 1 1 1 1 where i think he had the 1's only repeated 3 times ?

• IMO The difficulty is showing that $det(A - \lambda I) = 0$. Due to the denominators, it's not that easy to see how ERO could cancel out to give a row/column of 0's. Oct 15 '20 at 4:09