# Face-splitting product of two Vandermonde matrices: When is is invertible?

Let $$A$$ and $$B$$ be two $$n^2 \times n$$ Vandermonde matrices with coefficients $$\alpha_1,\ldots,\alpha_{n^2}$$ and $$\beta_1,\ldots,\beta_{n^2}$$. Let $$M$$ be the 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.)

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.
• 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) Oct 7, 2020 at 14:57
• 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}$. Oct 8, 2020 at 14:40