Vandermonde matrix | Abstract Algebra

Posts Tagged ‘Vandermonde matrix’

The Vandermonde determinant

Posted: September 12, 2022 in Basic Algebra, Matrices
Tags: Vandermonde matrix

One of the determinants that appear a lot in mathematics is the so-called Vandermonde determinant.

Definition. The $n \times n$ Vandermonde matrix is defined as follows

$\displaystyle V(x_1, \cdots , x_n):=\begin{pmatrix}1 & x_1 & \cdots & x_1^{n-1} \\ 1 & x_2 & \cdots & x_2^{n-1} \\ \vdots & \vdots & \cdots & \vdots \\ 1 & x_n & \cdots & x_n^{n-1}\end{pmatrix}.$

The determinant of the matrix $V(x_1, \cdots ,x_n)$ is called the Vandermonde determinant.

Of course, the value of $\det V(x_1, \cdots , x_n)$ is quite well-known but let’s find it anyway.

Remark 1. Expanding along the first row, gives

$\det V(0,x_2, \cdots ,x_n)=x_2 \cdots x_n \det V(x_2, \cdots x_n).$

Problem 1. Show that

$\displaystyle \det V(x_1, \cdots ,x_n)=\prod_{n \ge i > j \ge 1}(x_i-x_j).$

Solution. The proof is by induction on $n.$ For $n=2$ we have $\det V(x_1,x_2)=x_2-x_1.$ For the general case, first note that if one of the $x_i$ ‘s is zero, say $x_1=0,$ then, by Remark 1,

$\det V(x_1, \cdots ,x_n)=\det V(0,x_2, \cdots ,x_n)=x_2 \cdots x_n \det V(x_2, \cdots ,x_n)$

and we are done by induction. Suppose now that $x_i \ne 0$ for all $i.$ Consider the function

$p(t):=\det V(t,x_2, \cdots ,x_n),$

which is clearly a polynomial of degree at most $n-1.$ It is also clear that $p(x_2)= \cdots p(x_n)=0.$ Thus $p(t)=c(t-x_2) \cdots (t-x_n),$ for some constant $c.$ Now, using Remark 1,

$(-1)^{n-1}cx_2 \cdots x_n=p(0)=\det V(0, x_2, \cdots , x_n)= x_2 \cdots x_n \det V(x_2, \cdots , x_n),$

which gives $c=(-1)^{n-1}\det V(x_2, \cdots , x_n).$ Hence

$\begin{aligned}p(t)=(-1)^{n-1}(t-x_2) \cdots (t-x_n)\det V(x_2, \cdots , x_n)=(x_2-t) \cdots (x_n-t)\det V(x_2, \cdots , x_n)\end{aligned}$

and so $\det V(x_1, \cdots , x_n)=p(x_1)=(x_2-x_1) \cdots (x_n-x_1)\det V(x_2, \cdots , x_n).$ We are now done by induction. $\ \Box$

Remark 2. By Problem 1, $V(x_1, \cdots , x_n)$ is invertible if and only if $x_i \ne x_j$ for all $i \ne j.$

We now use Problem 1 to find the determinant of a slightly more complicated matrix.

Problem 2. Let $A$ be the $n \times n$ matrix whose $(i,j)$ -entry is $(x_i+y_j)^{n-1}.$ Show that

$\displaystyle \det A=\prod_{k=1}^{n-1}\binom{n-1}{k}\prod_{n \ge i > j \ge 1}(x_i-x_j)(y_j-y_i).$

Solution. Since

$\displaystyle (x_i+y_j)^{n-1}=\sum_{k=0}^{n-1}\binom{n-1}{k}x_i^ky_j^{n-1-k},$

we have $A=BC,$ where

$\displaystyle B=\begin{pmatrix}1 & \binom{n-1}{1}x_1 & \cdots & \binom{n-1}{n-1}x_1^{n-1} \\ 1 & \binom{n-1}{1}x_2 & \cdots & \binom{n-1}{n-1}x_2^{n-1} \\ \vdots & \vdots & \cdots & \vdots \\ 1 & \binom{n-1}{1}x_n & \cdots & \binom{n-1}{n-1}x_n^{n-1}\end{pmatrix}, \ \ \ \ \ \ C=\begin{pmatrix}y_1^{n-1} & y_2^{n-1} & \cdots & y_n^{n-1} \\ y_1^{n-2} & y_2^{n-2} & \cdots & y_n^{n-2} \\ \vdots & \vdots & \cdots & \vdots \\ 1 & 1 & \cdots & 1\end{pmatrix}.$

Thus $\det A=\det B \det C.$ Clearly

$\displaystyle \det B=\prod_{k=1}^{n-1}\binom{n-1}{k}\det V(x_1, \cdots ,x_n)=\prod_{k=1}^{n-1}\binom{n-1}{k}\prod_{n \ge i > j \ge 1}(x_i-x_j),$

by Problem 1. To find $\det C,$ note that swapping columns of $C^T,$ the transpose of $C,$ gives

$\displaystyle \det C=\det C^T=(-1)^{n(n-1)/2} \det V(y_1, \cdots , y_n)=\prod_{n \ge i > j \ge 1}(y_j-y_i),$

by Problem 1. $\ \Box$

Circulant matrix

Posted: September 2, 2022 in Basic Algebra, Matrices
Tags: circulant matrix, determinant, diagonalizable, eigenvalue, eigenvector, Vandermonde matrix

Definition. Given a vector $\bold{v}=(c_0, c_1, \cdots ,c_{n-1}) \in \mathbb{C}^n,$ the circulant (or cyclic) matrix generated by $\bold{v}$ is the $n \times n$ matrix $C(\bold{v})$ defined as follows

$C(\bold{v})=\begin{pmatrix}c_0 & c_1 & c_2 & \cdots & c_{n-2} & c_{n-1} \\ c_{n-1} & c_0 & c_1 & \cdots & c_{n-3} & c_{n-2} \\ c_{n-2} & c_{n-1} & c_0 & \cdots & c_{n-4} & c_{n-3} \\ \vdots & \vdots & \vdots & \cdots & \vdots & \vdots \\ c_1 & c_2 & c_3 & \cdots & c_{n-1} & c_0 \end{pmatrix}.$

Theorem. Let $\bold{v}=(c_0, c_1, \cdots ,c_{n-1}) \in \mathbb{C}^n,$ and $p(x)=c_0+c_1x + \cdots + c_{n-1}x^{n-1}.$ Let $\alpha \in \mathbb{C}$ be such that $\alpha^n=1,$ and let $\alpha_k:=e^{2k\pi i/n}, \ 0 \le k \le n-1.$ Let $\bold{x}(\alpha)=(1, \alpha, \alpha^2, \cdots , \alpha^{n-1})^T,$ where $T$ means transpose.

i) $C(\bold{v}) \bold{x}(\alpha)=p(\alpha)\bold{x}(\alpha).$

ii) The vectors $\bold{x}(\alpha_k), \ 0 \le k \le n-1,$ are $\mathbb{C}$ -linearly independent.

iii) The eigenvalues of $C(\bold{v})$ are $\lambda_k=p(\alpha_k), \ 0 \le k \le n-1,$ and $\bold{x}(\alpha_k)$ is an eigenvector corresponding to $\lambda_k.$ In particular, $C(\bold{v})$ is diagonalizable and

$\displaystyle \det C(\bold{v})=\prod_{k=0}^{n-1}(c_0+c_1\alpha_k+ \cdots + c_{n-1}\alpha_k^{n-1}).$

Proof. i) Using $\alpha^n=1,$ we have

$\begin{matrix} p(\alpha)=c_0+c_1\alpha + c_2\alpha^2+ \cdots +c_{n-2}\alpha^{n-2}+c_{n-1}\alpha^{n-1} \\ \\ \alpha p(\alpha)=c_{n-1} + c_0\alpha + c_1 \alpha^2 + \cdots +c_{n-3}\alpha^{n-2}+ c_{n-2}\alpha^{n-1}, \\ \\ \alpha^2p(\alpha)=c_{n-2}+c_{n-1}\alpha + c_0\alpha^2 + \cdots +c_{n-4}\alpha^{n-2}+ c_{n-3}\alpha^{n-1}, \\ \\ \vdots \\ \\ \alpha^{n-1}p(\alpha)=c_1+c_2\alpha+c_3\alpha^2+ \cdots + c_{n-1}\alpha^{n-2}+c_0\alpha^{n-1}.\end{matrix}$

The matrix form of the above identities is

$\begin{pmatrix}c_0 & c_1 & c_2 & \cdots & c_{n-2} & c_{n-1} \\ c_{n-1} & c_0 & c_1 & \cdots & c_{n-3} & c_{n-2} \\ c_{n-2} & c_{n-1} & c_0 & \cdots & c_{n-4} & c_{n-3} \\ \vdots & \vdots & \vdots & \cdots & \vdots & \vdots \\ c_1 & c_2 & c_3 & \cdots & c_{n-1} & c_0 \end{pmatrix}\begin{pmatrix} 1 \\ \alpha \\ \alpha^2 \\ \vdots \\ \alpha^{n-1}\end{pmatrix}=p(\alpha)\begin{pmatrix} 1 \\ \alpha \\ \alpha^2 \\ \vdots \\ \alpha^{n-1}\end{pmatrix},$

which is $C(\bold{v}) \bold{x}(\alpha)=p(\alpha)\bold{x}(\alpha).$

ii) Suppose that $\sum_{k=0}^{n-1}z_k\bold{x}(\alpha_k)=0$ for some $z_k \in \mathbb{C}.$ Then $\sum_{k=0}^{n-1}z_k\alpha_k^j=0$ for all $0 \le j \le n-1,$ which, in matrix form, becomes

$\begin{pmatrix}1 & 1 & \cdots & 1 \\ \alpha_0 & \alpha_1 & \cdots & \alpha_{n-1} \\ \vdots & \vdots & \cdots & \vdots \\ \alpha_0^{n-1} & \alpha_1^{n-1} & \cdots & \alpha_{n-1}^{n-1}\end{pmatrix} \begin{pmatrix}z_0 \\ z_1 \\ \vdots \\ z_{n-1}\end{pmatrix}=\begin{pmatrix}0 \\ 0 \\ \vdots \\ 0\end{pmatrix}.$

Now, the $n \times n$ matrix on the left-hand side of the above is a Vandermonde matrix which is invertible because $\alpha_0, \cdots \alpha_{n-1}$ are pairwise distinct. Thus $z_k=0$ for all $k,$ proving the linear independence.

iii) Since $\alpha_k^n=1$ for all $0 \le k \le n-1,$ we have $C(\bold{v}) \bold{x}(\alpha_k)=p(\alpha_k)\bold{x}(\alpha_k),$ by i). Thus each $\lambda_k=p(\alpha_k)$ is an eigenvalue of $C(\bold{v})$ with the corresponding eigenvector $\bold{x}(\alpha_k).$ Since, by ii), $\bold{x}(\alpha_k), \ 0 \le k \le n-1,$ are $\mathbb{C}$ -linearly independent, $\lambda_k, \ 0 \le k \le n-1,$ are all the eigenvalues of $C(\bold{v})$ and the matrix $C(\bold{v})$ is diagonalizable. Finally,

$\displaystyle \det C(\bold{v})=\prod_{k=0}^{n-1}\lambda_k=\prod_{k=0}^{n-1}p(\alpha_k)=\prod_{k=0}^{n-1}(c_0+c_1\alpha_k + \cdots + c_{n-1}\alpha_k^{n-1}). \ \Box$

Applications of linear algebra in calculus (2)

Posted: May 15, 2021 in Basic Algebra, Matrices
Tags: calculus, Vandermonde matrix

Problem. Let $n \ge 2$ be an integer, and let $f: \mathbb{R} \to \mathbb{R}$ be a function which is $n$ times differentiable. Show that if $\displaystyle \lim_{x\to\infty}f(x)$ is a finite number and $\displaystyle \lim_{x\to\infty}f^{(n)}(x)=0,$ then $\displaystyle \lim_{x\to\infty}f^{(k)}(x)=0$ for all $1 \le k \le n-1.$ Here $f^{(k)}$ is the $k$ th derivative of $f.$

Solution. By Taylor’s theorem, for each $x \in \mathbb{R}$ and $1 \le k \le n-1$ there exists $x_k \in (x,x+k)$ such that

$\displaystyle \sum_{j=1}^{n-1}\frac{f^{(j)}(x)}{j!}k^j=f(x+k)-f(x)-\frac{f^{(n)}(x_k)}{n!}k^n,$

which, in terms of matrices, can be written as

$\displaystyle \begin{pmatrix}1 & 1 & \cdots & 1 \\ 2 & 2^2 & \cdots & 2^{n-1} \\ . & . & \cdots & . \\ . & . & \cdots & . \\ . & . & \cdots & . \\ n-1 & (n-1)^2 & \cdots & (n-1)^{n-1} \end{pmatrix}\begin{pmatrix}f'(x) \\ \frac{f''(x)}{2} \\ . \\ . \\ . \\ \frac{f^{(n-1)}(x)}{(n-1)!}\end{pmatrix}=\begin{pmatrix}g_1(x) \\ g_2(x) \\ . \\ . \\ . \\ g_{n-1}(x)\end{pmatrix}, \ \ \ \ \ \ \ \ (*)$

where

$\displaystyle g_j(x):=f(x+j)-f(x)-\frac{f^{(n)}(x_j)}{n!}j^n, \ \ \ \ \ 1 \le j \le n-1.$

Since the square matrix on the left-hand side of $(*)$ is invertible (Vandermonde), each $f^{(k)}(x)$ is a linear combination of the functions $g_1(x), \cdots , g_{n-1}(x).$ So, in order to prove that $\displaystyle \lim_{x\to\infty}f^{(k)}(x)=0$ for all $1 \le k \le n-1,$ we only need to show that $\displaystyle \lim_{x\to\infty}g_j(x)=0$ for all $1 \le j \le n-1.$ Well, for each $j,$ we have $\displaystyle \lim_{x\to\infty}(f(x+j)-f(x))=0$ because we are given that $\displaystyle \lim_{x\to\infty}f(x)$ is a finite number. We also have $\displaystyle \lim_{x\to\infty}f^{(n)}(x_j)=0$ because $\displaystyle \lim_{x\to\infty}f^{(n)}(x)=0$ and $x_j \in (x, x+j).$ Thus $\displaystyle \lim_{x\to\infty}g_i(x)=0$ for all $j. \ \Box$