17
$\begingroup$

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}$.

$\endgroup$
  • 1
    $\begingroup$ Have you checked if your matrix can be written as $N^H N$ for some matrix $N$ with complex entries? $\endgroup$ – Jack D'Aurizio Oct 13 '16 at 19:30
  • $\begingroup$ @JackD'Aurizio Is the $H$ in $N^H N$ a positive integer? $\endgroup$ – Sergio Parreiras Oct 13 '16 at 19:37
  • 1
    $\begingroup$ No, it stands for the Hermitian conjugate. $\endgroup$ – Jack D'Aurizio Oct 13 '16 at 19:37
  • $\begingroup$ @JackD'Aurizio: Thanks, I will check if the matrix admits such representation. $\endgroup$ – Sergio Parreiras Oct 13 '16 at 20:00
  • $\begingroup$ The generalization has been crossposted to math.stackexchange.com/questions/1962904/… now, apparently to give a place to post proofs after the bounty here has failed. Just mentioning. $\endgroup$ – darij grinberg Oct 19 '16 at 21:19
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ If the statement in the question is true, then by continuity this means $M$ must always have $n-1$ negative eigenvalues and one positive eigenvalue, so it is probably worth trying to work out what the positive eigenvector is in general and then trying to show that the restriction of $M$ to its orthogonal complement is negative definite. $\endgroup$ – Anton Malyshev Oct 17 '16 at 6:40
3
+450
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Notice that in the $i_\mathrm{th}$ row of $M$, there is no $x_i$ or $1-x_i$ term, but this does not seem to be true for $Q$. Are you sure that $Q=M$? $\endgroup$ – Sergio Parreiras Oct 17 '16 at 13:46
  • 1
    $\begingroup$ $M$ is not quite the matrix of $Q$, it is the matrix of $\hat Q(v_1, \dots, v_n) = Q(v_1/x_1, \dots, v_n/x_n).$ $\endgroup$ – Anton Malyshev Oct 17 '16 at 13:52
  • 1
    $\begingroup$ That would correspond to the hope that $Q$ restricted to the span of those vectors $w^i$ is negative definite. First of all, that's not true in general (consider taking one $x_i$ very very small compared to the rest), and second of all just checking that $Q(w^i)$ is negative doesn't in general guarantee that $Q$ is negative definite on the span of the $w^i$. $\endgroup$ – Anton Malyshev Oct 17 '16 at 16:50
  • 1
    $\begingroup$ I expect it to be somewhat tricky to find an appropriate $V$ of codimension 1 on which $Q$ is negative definite. One that's guaranteed to work, assuming the conjecture is true and $Q$ really does always have signature $(1,n-1)$, is the orthogonal complement to the positive eigenvector of $Q$. But finding that eigenvector seems tricky in the first place. Other "nearby" spaces should work and may be easier to describe and reason about. $\endgroup$ – Anton Malyshev Oct 17 '16 at 16:50
  • 1
    $\begingroup$ Actually, adding multiples of a rank 1 form $R$ doesn't change anything on the hyperplane of vectors where $R(v) = 0$, so the $R$ I mentioned won't do, and finding one that will do is equivalent to finding an appropriate hyperplane for the previous approach. $\endgroup$ – Anton Malyshev Oct 17 '16 at 17:23

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.