<p>Sorry if I am missing something, but isn't it always singular in your special case? The first column is identically <span class="math-container">$1$</span>, the second column is <span class="math-container">$(\beta_1,\ldots,\beta_{n^2})^T$</span>, and the <span class="math-container">$n+1$</span>'th column is <span class="math-container">$(\alpha_1,\ldots,\alpha_{n^2})^T$</span>. If <span class="math-container">$\beta_i=\alpha_i-1$</span> for all <span class="math-container">$1\leq i\leq n^2$</span>, then the <span class="math-container">$n+1$</span>'th column is a linear combination of the first and second columns, so it is singular, right?</p>
<p><strong>EDIT</strong>: in response to the amended question in the comments, I think it becomes nonsingular if and only if the <span class="math-container">$\alpha_i$</span> are distinct (note that one direction is obvious; if <span class="math-container">$\alpha_i=\alpha_j$</span> for some <span class="math-container">$i\neq j$</span>, then clearly there are two equal rows).</p>
<p>To see the other direction, suppose that the <span class="math-container">$\alpha_i$</span> are distinct, but the matrix is singular. This means the <span class="math-container">$n+1$</span>'th column is a linear combination of the previous <span class="math-container">$n$</span> columns. Defining <span class="math-container">$f_i(x)=x^i(x-1)^{n-i}$</span> for <span class="math-container">$i=0,\ldots,n$</span>, this means there exists <span class="math-container">$\lambda_0,\ldots,\lambda_{n-1}\in \mathbb{F}$</span> not all zero such that for all <span class="math-container">$i=1,\ldots,n+1$</span>,
<span class="math-container">\begin{equation}
f_{n}(\alpha_i) = \sum_{j=0}^{n-1} \lambda_j f_j(\alpha_i);
\end{equation}</span>
as this holds at <span class="math-container">$n+1$</span> distinct points, and both sides have degree <span class="math-container">$n$</span> in <span class="math-container">$x$</span>, this means that <span class="math-container">$f_n = \sum_{j=0}^{n-1} \lambda_j f_j$</span> as formal polynomials, as well as functions (the injectivity of the map between polynomials of degree at most <span class="math-container">$n$</span> and functions, when the field has at least <span class="math-container">$n+1$</span> elements, is essentially the nonsingularity of the Vandermonde matrix in the first place).</p>
<p>To see that this is not possible, note that evaluating both sides at <span class="math-container">$x=0$</span> shows that <span class="math-container">$\lambda_0 = 0$</span>, for all other terms vanish, so this coefficient must be zero because <span class="math-container">$f_0(0)\neq 0$</span>. Because all remaining terms are now divisible by <span class="math-container">$x$</span>, we may safely divide through and keep this linear relationship, and then apply the same argument to deduce that <span class="math-container">$\lambda_1=0$</span>, and so on. But this implies <span class="math-container">$f_n$</span> is formally the zero polynomial, which clearly does not hold. Therefore, the matrix has full column-rank and so is invertible.</p>

CC BY-SA 4.0
2020-10-07T14:57:45.660Z
Ah yes you are right in this case, thanks. What about this special case again, and where I don't do the full Kronecker products of the lines, but I keep only the product elements $\alpha_i^j (\alpha_i -1)^k$ when $j+k=n$? (and there are $n+1$ coefficients now to obtain a square matrix)
M.Monet
CC BY-SA 4.0
2020-10-07T16:00:40.473Z
@M.Monet see the edit. I hope it's right!
Jason Gaitonde
CC BY-SA 4.0
2020-10-08T14:40:53.020Z
Ah yes indeed it is invertible in this special subcase :) It can also be seen that this matrix is the product of a diagonal matrix with entries $\alpha_i^n$ and of a Vandermonde with coefficients $\frac{\alpha_i - 1}{\alpha_i}$.
M.Monet
CC BY-SA 4.0
2020-10-07T14:23:31.907Z
2020-10-07T16:00:25.013Z
2020-10-07T16:00:25.013Z
Jason Gaitonde
<p>Let <span class="math-container">$A$</span> and <span class="math-container">$B$</span> be two <span class="math-container">$n^2 \times n$</span> <a href="https://en.wikipedia.org/wiki/Vandermonde_matrix" rel="nofollow noreferrer">Vandermonde matrices</a> with coefficients <span class="math-container">$\alpha_1,\ldots,\alpha_{n^2}$</span> and <span class="math-container">$\beta_1,\ldots,\beta_{n^2}$</span>. Let <span class="math-container">$M$</span> be the <a href="https://en.wikipedia.org/wiki/Khatri%E2%80%93Rao_product#Face-splitting_product" rel="nofollow noreferrer">face-splitting product</a> of <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, that is, the <span class="math-container">$n^2 \times n^2$</span> matrix whose <span class="math-container">$(i,kn+l)$</span> entry is <span class="math-container">$A_{i,k+1} \times B_{i,l} = \alpha_i^{k} \beta_i^{l-1}$</span> for <span class="math-container">$0 \leq k \leq n-1$</span> and <span class="math-container">$1 \leq l \leq n$</span>.</p>
<p><strong>Question:</strong> <em>When does <span class="math-container">$M$</span> have full rank?</em> Or, alternatively, what is the determinant of <span class="math-container">$M$</span> as a function of the <span class="math-container">$\alpha$</span>s and <span class="math-container">$\beta$</span>s?</p>
<p>I have tried to compute the determinant as one usually does with a Vandermonde matrix but this quickly becomes very messy, and so I was wondering if there was a simpler way of obtaining that.</p>
<p><strong>Edit:</strong> Actually the answer in the special case where <span class="math-container">$\beta_i = \alpha_i - 1$</span> for all <span class="math-container">$1 \leq i \leq n^2$</span> would be sufficient for my needs.</p>
<p>(Just to give some context, I am trying to show that a certain problem is #P-hard; I can do polynomial interpolation from counting the number of perfect matchings of a graph, but I end up on a matrix that is similar to <span class="math-container">$M$</span> and now I need it to be invertible.)</p>

<linear-algebra><matrix-product>
Face-splitting product of two Vandermonde matrices: When is is invertible?
M.Monet
# Face-splitting product of two Vandermonde matrices: When is is invertible?

(Asked by: username_0 on 2020-10-06)

Let $A$ and $B$ be two $n^2 \times n$ [Vandermonde matrices](https://en.wikipedia.org/wiki/Vandermonde_matrix) with coefficients $\alpha\_1,\ldots,\alpha\_{n^2}$ and $\beta\_1,\ldots,\beta\_{n^2}$. Let $M$ be the [face-splitting product](https://en.wikipedia.org/wiki/Khatri%E2%80%93Rao_product#Face-splitting_product) of $A$ and $B$, that is, the $n^2 \times n^2$ matrix whose $(i,kn+l)$ entry is $A\_{i,k+1} \times B\_{i,l} = \alpha\_i^{k} \beta\_i^{l-1}$ for $0 \leq k \leq n-1$ and $1 \leq l \leq n$.

**Question:** *When does $M$ have full rank?* Or, alternatively, what is the determinant of $M$ as a function of the $\alpha$s and $\beta$s?

I have tried to compute the determinant as one usually does with a Vandermonde matrix but this quickly becomes very messy, and so I was wondering if there was a simpler way of obtaining that.

**Edit:** Actually the answer in the special case where $\beta\_i = \alpha\_i - 1$ for all $1 \leq i \leq n^2$ would be sufficient for my needs.

(Just to give some context, I am trying to show that a certain problem is #P-hard; I can do polynomial interpolation from counting the number of perfect matchings of a graph, but I end up on a matrix that is similar to $M$ and now I need it to be invertible.)

**Tags:** linear-algebra, matrix-product


---

## 1 answers

### Answer by username_1 on 2020-10-07. Score: 2

Sorry if I am missing something, but isn't it always singular in your special case? The first column is identically $1$, the second column is $(\beta\_1,\ldots,\beta\_{n^2})^T$, and the $n+1$'th column is $(\alpha\_1,\ldots,\alpha\_{n^2})^T$. If $\beta\_i=\alpha\_i-1$ for all $1\leq i\leq n^2$, then the $n+1$'th column is a linear combination of the first and second columns, so it is singular, right?

**EDIT**: in response to the amended question in the comments, I think it becomes nonsingular if and only if the $\alpha\_i$ are distinct (note that one direction is obvious; if $\alpha\_i=\alpha\_j$ for some $i\neq j$, then clearly there are two equal rows).

To see the other direction, suppose that the $\alpha\_i$ are distinct, but the matrix is singular. This means the $n+1$'th column is a linear combination of the previous $n$ columns. Defining $f\_i(x)=x^i(x-1)^{n-i}$ for $i=0,\ldots,n$, this means there exists $\lambda\_0,\ldots,\lambda\_{n-1}\in \mathbb{F}$ not all zero such that for all $i=1,\ldots,n+1$,
\begin{equation}
f\_{n}(\alpha\_i) = \sum\_{j=0}^{n-1} \lambda\_j f\_j(\alpha\_i);
\end{equation}
as this holds at $n+1$ distinct points, and both sides have degree $n$ in $x$, this means that $f\_n = \sum\_{j=0}^{n-1} \lambda\_j f\_j$ as formal polynomials, as well as functions (the injectivity of the map between polynomials of degree at most $n$ and functions, when the field has at least $n+1$ elements, is essentially the nonsingularity of the Vandermonde matrix in the first place).

To see that this is not possible, note that evaluating both sides at $x=0$ shows that $\lambda\_0 = 0$, for all other terms vanish, so this coefficient must be zero because $f\_0(0)\neq 0$. Because all remaining terms are now divisible by $x$, we may safely divide through and keep this linear relationship, and then apply the same argument to deduce that $\lambda\_1=0$, and so on. But this implies $f\_n$ is formally the zero polynomial, which clearly does not hold. Therefore, the matrix has full column-rank and so is invertible.

> **Comments:**
> **username_0**: Ah yes you are right in this case, thanks. What about this special case again, and where I don't do the full Kronecker products of the lines, but I keep only the product elements $\alpha_i^j (\alpha_i -1)^k$ when $j+k=n$? (and there are $n+1$ coefficients now to obtain a square matrix)  
> **username_1**: @username_0 see the edit. I hope it's right!  
> **username_0**: Ah yes indeed it is invertible in this special subcase :) It can also be seen that this matrix is the product of a diagonal matrix with entries $\alpha_i^n$ and of a Vandermonde with coefficients $\frac{\alpha_i - 1}{\alpha_i}$.  

---

