1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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) $\endgroup$ – M.Monet Oct 7 '20 at 14:57
  • $\begingroup$ @M.Monet see the edit. I hope it's right! $\endgroup$ – J.G Oct 7 '20 at 16:00
  • $\begingroup$ 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}$. $\endgroup$ – M.Monet Oct 8 '20 at 14:40

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.