Invertibility of combinatorial matrix

Your matrix is the adjacency matrix of the Kneser graph $KG_{n, k}$ (using the notation from the Wikipedia article). Its eigenvalues are known; here is a quote from the Wikipedia:

For $j=0,\ldots,k$, the eigenvalue $\lambda_j=(-1)^j\dbinom{n-k-j}{k-j}$ occurs with multiplicity $\dbinom{n}{j}-\dbinom{n}{j-1}$ for $j > 0$ and $1$ for $j = 0$. See this paper for a proof.

This is also proved in

• Corollary 6.6.1 of Chris Godsil, Karen Meagher, Erdös–Ko–Rado Theorems: Algebraic Approaches, Cambridge University Press 2016.

• Theorem 1 of Philipp Reinfeld, Chromatic Polynomials and the Spectrum of the Kneser Graph (freely available).

The oft-given reference to Godsil and Royle, Algebraic Graph Theory seems wrong: they only appear to prove the set of eigenvalues, not their multiplicities. (Although the multiplicities might follow from their argument, if there is a way to lift them through an equitable partition.)

Note that the words "with multiplicity $\dbinom{n}{j}-\dbinom{n}{j-1}$ for $j > 0$ and $1$ for $j = 0$" can be replaced by "with multiplicity $\dbinom{n}{j}-\dbinom{n}{j-1}$", since $\dbinom{n}{j}-\dbinom{n}{j-1}$ equals $0$ when $j = 0$.

As you know, the determinant of a matrix is the product of its eigenvalues. Thus, the above formula for the eigenvalues yields that the determinant of your matrix is \begin{align} \prod_{j=0}^k \left(\left(-1\right)^j \dbinom{n-k-j}{k-j}\right)^{\dbinom{n}{j}-\dbinom{n}{j-1}} \neq 0 \end{align} (since all $\dbinom{n-k-j}{k-j}$ are positive integers when $k \leq n/2$).

An idea only

W.l.g. let all the elements of $I$ which contain $1$ come first when forming your matrix.

Then the matrix has the form $\begin{pmatrix}O&B \\B^T&D\\\end{pmatrix}$ and its determinant is $$|O-BD^{-1}B^T||D|=|BD^{-1}B^T||D|.$$ Since we can assume $D$ is invertible by induction, we require $|BD^{-1}B^T|$ to be non-zero.

Disclaimer : this isn't a solution. It has to be considered as a hint complementing the indications provided by S. Dolan.

Let us write matrix $A$ under the form $A_{n,p}$.

Here is an example : the representation of $A_{10,2}$ (therefore with dimension $45 \times 45$) with a recursive structure of the form given by S. Dolan :

$$A_{n,p}=\begin{pmatrix}0&B\\B^T&A_{n-1,p}\end{pmatrix}$$

Fig. 1 : Graphical representation of $A_{10,2}$ : zeros in dark blue ; ones in light blue.

We remark a pretty block structure. Why do we have it ?

It is due to the fact that we have chosen to rank the different combinations (subsets with 2 elements) in lexicographic order, i.e :

$$\begin{array}{rr} \color{red}{1}&2,\\ \color{red}{1}&3,\\ \color{red}{1}&4,\\ \color{red}{1}&5,\\ \color{red}{1} & 6, \\ \color{red}{1} & 7, \\ \color{red}{1} & 8, \\ \color{red}{1} & 9, \\ \color{red}{1} & 10,\end{array} \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rr} 2 & 3, \\ 2 & 4, \\ 2 & 5, \\ 2 & 6, \\ 2 & 7, \\ 2 & 8, \\ 2 & 9, \\ 2 & 10, \end{array} \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rr} 3 & 4, \\ 3 & 5,\\ \cdots & \cdots \\ 7 & 8, \\ 7 & 9, \\ 7 & 10, \\ 8 & 9, \\ 8 & 10, \\ 9 & 10. \end{array}$$

The first 9 subsets with 2 elements (indexing the first 9 lines and columns) all with common element "1", explain in particular why the $9 \times 9$ upper left block is zero, the next 8 subsets with 2 elements account for the diagonal block $8 \times 8$, etc.

Therefore it is not surprising that once we get rid of the first $10$ cases where figure $\color{red}{1}$ is present, we fall "recursively" into the previous case with only $9$ elements.

Remark : we shouldn't be surprized that the dimensions match : we have

$$1+2+3+\cdots + 9=\dfrac{9 \times (9+1)}{2}=45,$$

a particular case of $\sum_{k=1}^n k=\dfrac{n(n+1)}{2}.$

Now, let us change $p$ from $2$ to $3$, keeping $n=10$. We get the following matrix, which has still a different structure :

Fig. 2 : (Art Nouveau ?) Matrix $A_{10,3}$ with the same color conventions as in Fig. 1. The diagonal block dimensions are $36 \times 36$, (where $36=\binom{9}{2}=\tfrac{9 \times 8}{2}$), $28 \times 28$, $21 \times 21$,...

Related (for $2^n \times 2^n$ matrices) : Determinant of matrix defined by set partition, Invertibility of Set Intersection Signed matrix, https://math.stackexchange.com/q/1361250