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

Question

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.)

Answer 1

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.