Prove that determinant of a matrix (with polynomial entries) is non-zero

Question

For $\mathbf x\in\mathbb (0,1)^n$ with $n>2$ and a positive integer $1\le k<n$, define the mapping $f_{i,j}\colon (0,1)^n\rightarrow (0,1)$ by, $$f_{i,j}(\mathbf x)= \sum\limits_{\substack{\mathcal A \subset \{ 1,\ldots,n\}\backslash \{i,j\}\\ |\mathcal A|=k-1}}\quad\left( \prod\limits_{l\not\in \mathcal A\cup \{i,j\} }x_l\,\,\cdot\!\!\!\! \prod\limits_{ l\in \mathcal A}(1-x_l)\right).$$

Convention: if the set of indexes is empty, the product is one.

I'm trying to prove that the matrix $$M=\begin{cases} m_{i,j}=f_{i,j}(\mathbf{x})\quad &\text{ if } j\neq i,\\ m_{i,j}=0&\text{ if } j=i\end{cases}$$ has full-rank, i.e. $\det(M)\neq 0$ (for $\mathbf{x}$ in $(0,1)^n$).

I proved this for two particular cases: $k=1$, $f_{i,j}(\mathbf x)= \prod\limits_{ k\neq i,j} x_k$ and so that case is quite easy. Also if $k=n-1$, $f_{i,j}(\mathbf x)= \prod\limits_{ k\neq i,j} (1-x_k)$, which is also an easy case. However, for $1<k<n-1$, I can only solve by using brute force. For example, for $k=2$ and $n=4$, the matrix is: $$\left(\begin{array}{cccc}0 & x_3(1-x_4)+x_4(1-x_3) & x_2(1-x_4)+x_4(1-x_2) & x_2(1-x_3)+x_3(1-x_2) \\ x_3(1-x_4)+x_4(1-x_3) & 0 & x_1(1-x_4)+x_4(1-x_1) & x_1(1-x_3)+x_3(1-x_1) \\ x_2(1-x_4)+x_4(1-x_2) & x_1(1-x_4)+x_4(1-x_1) & 0 & x_1(1-x_2)+x_2(1-x_1) \\x_2(1-x_3)+x_3(1-x_2) & x_1(1-x_3)+x_3(1-x_1) & x_1(1-x_2)+x_2(1-x_1) & 0\end{array}\right),$$ and using Mathematica, it can be shown that the determinant of $M$ is not zero for $\mathbf x \in (0,1)^4$.

But I'm lost trying to tackle the general case: any suggestions/hints (i.e., they need to be full answers) are very welcome.

Update: For several examples$-$ if we set $f_{i,j}(\mathbf x,\mathbf y)= \sum\limits_{\substack{\mathcal A \subset \{ 1,\ldots,n\}\backslash \{i,j\}\\ |\mathcal A|=k-1}}\quad\left( \prod\limits_{l\not\in \mathcal A\cup \{i,j\} }x_l\,\,\cdot\!\!\!\! \prod\limits_{ l\in \mathcal A}y_l\right)$, and compute the determinante of $M$ above. It is easy to see by inspection that all of terms of $\mathrm{det}(M)$ have the same signal. Perhaps, it would be easier to prove the result for this more general $f_{i,j}$.

Answer 1

I think you are asking if the matrix has full rank for all ${\bf x}\in (0,1)^n$. I can show that the matrix has full rank for some ${\bf x}\in (0,1)^n$.

The matrix has full rank when all variables are assigned the same value $x\in (0,1)$. Under this assignment the matrix becomes

$$ \left[\begin{array}{cccc} 0&r&\cdots&r\\ r&0&\cdots&r\\ \vdots&\vdots&\ddots&\vdots\\ r&r&\cdots&0 \end{array} \right] = r(J-I) $$ where $r = \binom{n-2}{k-1}x^{n-k-1}\left(1-x\right)^{k-1}$, $I$ is the $n\times n$ identity matrix, and $J$ is the $n\times n$ matrix of all $1$'s.

The matrix $J$ has rank 1 and trace $n$, so its e-values are $0$ (multiplicity $n-1$) and $n$ (multiplicity $1$). Therefore the e-values of $J-I$ are $-1$ (multiplicity $n-1$) and $n-1$ (multiplicity $1$). Hence the determinant of $J-I$ is $(-1)^{n-1}(n-1)$. Hence the determinant of your matrix, after every variable has been assigned the value $x$, is $(-1)^{n-1}(n-1)\left[\binom{n-2}{k-1}x^{n-k-1}\left(1-x\right)^{k-1}\right]^n$, which is not zero when $x\in (0,1)$.

Answer 2

A possibly useful way to rephrase the question:

For any subset $\mathcal A \subseteq \{1, 2, \dots, n\}$, let

$$p_{\mathcal A} = \prod_{i \in \mathcal A} x_i \prod_{i\notin \mathcal A} (1-x_i),$$

and let $Q_\mathcal A$ denote the quadratic form on $\mathbb R^n$ given by

$$Q_\mathcal A (v) = \left(\sum_{i \in \mathcal A}v_i\right)^2 - \sum_{i \in\mathcal A} v_i^2 = \sum_{i,j \in \mathcal A, i\neq j}v_i v_j.$$

Consider the quadratic form $$Q = \sum_{\mathcal A} p_\mathcal A Q_\mathcal A,$$ where we sum over subsets of size $n-(k-1)$. Up to a diagonal change of coordinates, the matrix of this quadratic form is the matrix in the question. So the goal is to show that $Q$ is a nondegenerate quadratic form.

It appears that $Q$ has signature $(1, n-1)$. Since it's easy to find a one-dimensional subspace of $\mathbb R^n$ on which $Q$ is positive definite, it suffices to find a codimension 1 subspace $V$ of $\mathbb R^n$ on which $Q$ is negative definite.

Note that up to scaling $Q$ is the expected value of $Q_\mathcal A$, where $\mathcal A$ is chosen via independent Bernoulli trials with probability $x_i$ for each event $i \in \mathcal A$, but conditioned on $|\mathcal A| = n-(k-1)$. Sensible candidates for $V$ might be orthogonal complements to vectors of the form $(v_1, \dots, v_n)$ where $v_i$ is somehow related to this probability distribution, e.g. $v_i = x_i$, or $v_i = x_i/(1-x_i)$, or $v_i = \mathbb P(i \in \mathcal A)$.