8
$\begingroup$

I'm following the book Mimetic Discretization Methods by Castillo and Miranda, reading the page 209-211, it states the following:

Let $V(m;G)$ be a Vandermonde matrix, of order $m$ with generator $G = \{ g_1, g_2, \ldots, g_n \}$. Where the order implies the highest power of Vandermonde matrix, therefore $V(m;G)$ has $(m+1)$ rows and $n$ columns.

Let \begin{align} G_1 &= \{ -1/2, 1/2, 3/2, 5/2, 7/2, 9/2 \} \\ G_2 &= \{ -3/2, -1/2, 1/2, 3/2, 5/2, 7/2 \} \\ G_3 &= \{ -5/2, -3/2, -1/2, 1/2, 3/2, 5/2 \} \\ G_4 &= \{ -7/2, -5/2, -3/2, -1/2, 1/2, 3/2 \} \end{align}

Generators of the following matrices

\begin{align} V_1 &=V(4;G_1) \\ V_2 &=V(4;G_2) \\ V_3 &= V(4;G_3) \\ V_4 &= V(4;G_4) \end{align}

Just for sake of example $V_1$ looks like:

\begin{align} V_1 = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 \\ -1/2 & 1/2 & 3/2 & 5/2 & 7/2 & 9/2 \\ (-1/2)^2 & (1/2)^2 & (3/2)^2 & (5/2)^2 & (7/2)^2 & (9/2)^2 \\ (-1/2)^3 & (1/2)^3 & (3/2)^3 & (5/2)^3 & (7/2)^3 & (9/2)^3 \\ (-1/2)^4 & (1/2)^4 & (3/2)^4 & (5/2)^4 & (7/2)^4 & (9/2)^4 \\ \end{bmatrix} \end{align}

The null space of this matrix is given by $Ker(V_1) =[-1 \; 5 \; -10\; 10\; -5\; 1]^T$, that is easily verifiable just by $V_1 \cdot Ker(V_1)$ that results in the null vector, as expected.

The other Vandermonde matrices $V_2, V_3, V_4$ share the same null space. The book then states:

In general, the null space of a $k$-th order Vandermonde matrix has dimension $\frac{1}{2}k -1$.

My first question: There is no references or proofs to support this claim. Is this true? How can I prove that? What are conditions to that be true. I could not find anywhere this affirmation.

The text continues, and we need to solve the following system

\begin{equation} V_i a_i^T = b \end{equation}

Where $V_i$ are the Vandermonde matrices above, $a_i$ is a unknown vector and $b = [ 0 \;1 \;0 \;0\; 0 ]$

Lets only focus in $i=1$ since the construction to other matrices are equivalent. We then need to solve the following:

\begin{equation} V_1 a_1^T = b \end{equation}

completely written as

\begin{equation} \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 \\ -1/2 & 1/2 & 3/2 & 5/2 & 7/2 & 9/2 \\ (-1/2)^2 & (1/2)^2 & (3/2)^2 & (5/2)^2 & (7/2)^2 & (9/2)^2 \\ (-1/2)^3 & (1/2)^3 & (3/2)^3 & (5/2)^3 & (7/2)^3 & (9/2)^3 \\ (-1/2)^4 & (1/2)^4 & (3/2)^4 & (5/2)^4 & (7/2)^4 & (9/2)^4 \\ \end{bmatrix}\begin{bmatrix} a_{11} \\a_{12} \\a_{13} \\a_{14} \\a_{15} \\a_{16} \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} \end{equation}

Then the text declares that

\begin{align} a_1 = \left[ -\frac{11}{12} \, \frac{17}{24} \, \frac{3}{8} \, -\frac{5}{24} \, \frac{1}{24} \, 0 \right] + \alpha_1 Ker(V_1) \end{align}

for some $\alpha_1 \in \mathbb{R}$.

My second question is: where that vector in first term came from? Is that true? How can I show that?

I'm able to solve that system using least squares, but could not find a correlation.

Some tries: (EDIT)

Definition (Null Space): $Ker(V)$ is a null space of $V$ if an only if $V \cdot \alpha Ker(V) = \vec{0}$ for any $\alpha \in \mathbb{R}$.

Lets say by hypothesys that

\begin{align} a &= x + \alpha Ker(V) \end{align}

Since we are looking for (I will drop the indexes for sake of notation and typing):

\begin{align} V \cdot a &= b \\ a &= V^{-1} b \end{align} by the hypothesis \begin{align} x + \alpha Ker(V) &= V^{-1} b \\ Vx + V \left( \alpha Ker(V) \right) &= b \end{align} by Null Space definition \begin{align} Vx &= b \end{align}

We are just back where we started, seems a tautology in my view.

Anyway I also know that

\begin{align} a &= x + \alpha Ker(V) \\ x &= a - \alpha Ker(V) \end{align}

I can find $a$ by least squares, and have $Ker(V)$ by the null space analysis. Therefore I just need to find $\alpha$ to uniquely identify $x$.

$\endgroup$
  • 1
    $\begingroup$ Are you sure it's stated as “the null space of an $m$-th order Vandermonde matrix has dimension $\dfrac m2-1$”? For $n=|G|=m+1$, $V(m; G)$ is invertible and thus the dimension is $0$. $\endgroup$ – Saad Jun 23 '18 at 7:36
  • $\begingroup$ Also $\frac{m}{2}-1$ is not necessarily an integer...also en.wikipedia.org/wiki/Vandermonde_matrix#Resulting_properties $\endgroup$ – Reinstate Monica Jun 25 '18 at 20:26
1
+50
$\begingroup$

EDIT. We consider $V(m,G)\in M_{m+1,n}$ where we assume that $n\geq m+1$.

i) Thus $V(m,G):\mathbb{R}^n\rightarrow \mathbb{R}^{m+1}$. The first $m+1$ columns of $V$ realize the transpose of a standard square Vandermonde matrix $W$ which is invertible.

cf. https://en.wikipedia.org/wiki/Vandermonde_matrix

Thus $rank(V)=m+1$ ($V$ is surjective) and $dim(\ker(V))=n-m-1$.

In your example, $n=3m/2$, that implies $dim(\ker(V))=m/2-1$.

ii) We want to solve the equation in $x$, $Vx=e_2$. Since $V$ is surjective, there is particular solution $x_0$. If $x$ is the general solution, then $V(x_0)=V(x)$ $\iff$ $V(x-x_0)=0$ $\iff$ $x-x_0\in \ker(V)$ $\iff$ $x\in x_0+\ker(V)$. Finally, the set of solutions is $x_0+\ker(V)$.

We search $x_0$ in the form $[p,q,r,s,t,0]^T$. Then the equation to solve is equivalent to $W[p,q,r,s,t]^T=e_2$, where $W$ is the above invertible matrix. You can solve this last equation by Gauss method and obtain the unique solution $[-11/12,17/24,3/8,-5/24,1/24]^T$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Loup, can you point any reference or proof about invertibility of any Vandermonde matrix of n-th order? $\endgroup$ – Lin Jun 25 '18 at 10:20
  • $\begingroup$ Loup about ii, can you please elaborate the following statement in ttfont: "If $Vx=Vy$, then $x−y \in Ker(V)$ and the set of solutions is x=x0+ker(V) where x0 is a particular solution". That is exactly where I'm struggling, I'm probably missing some definition or theorem. $\endgroup$ – Lin Jun 25 '18 at 10:34
  • $\begingroup$ cf. my edit in my answer. $\endgroup$ – user91684 Jun 25 '18 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.