A matrix problem with line-sums

03:07:00  

Last week, one of my junior gave me a Linear Algebra / Matrix problem, which smell like a combinatorial problem (although until now, I haven't found a combinatorial proof of it).

Let $X$ and $Y$ be a $n \times n$  $(0,1)$-matrix , where the line-sums of $X$ (resp. $Y$) is equal to $k$ (resp. $k+1$). Suppose that   $$\begin{equation} XY=(k-\lambda)I_n + \lambda J\end{equation}$$ where $J$ is the $n \times n$ matrix with all entries equal $1$, and $I_n$ is identity matrix. If $1+4(k-\lambda)$ is not a perfect square prove that $n=4\lambda +1$ and $k=2 \lambda$.  

Here is a combinatorial version of the above

Let $A=\{1,2,..,n\}$ and suppose that we have $2n$ subsets of $A$, say $X_1, X_2, ..., X_n$ and $Y_1, Y_2, ..., Y_n$, where each subsets satisfy:

• $|Y_i| = |X_i|+1 = k+1$ for all $i=1,2,...,n$.

• For each $x \in A$, there are exactly $k$ subsets $X_{i_1}, X_{i_2}, ..., X_{i_k}$ and exactly $k+1$ subsets $Y_{i_1}, Y_{i_2}, ..., Y_{i_{k+1}}$ which contain $x$.

•  For any $i=1,2,..,n$ we have $|X_i \cap Y_i| = k$ and while for any $1 \leq i < j \leq n$ we have $|X_i \cap Y_j| = \lambda$.

If $1+4(k-\lambda)$ is not a perfect square prove that $n=4\lambda +1$ and $k=2 \lambda$.

After awhile I found a proof using eigenvalues. But now,  I'm actually interested on a combinatorial proof of this one,  the condition $1+4(k-\lambda)$ condition seems to be does not have any trivial combinatorial interpretation.

But I will give a sketch of Linear-Algebra proof on this post.
Notice that the Right-Hand-Side is just the matrix
$$H(k,\lambda)=\begin{pmatrix} k & \lambda & \cdots & \cdots & \lambda \\ \lambda & k &\cdots & \cdots & \lambda \\ \lambda & \lambda & \ddots & \cdots & \lambda \\ \vdots & \vdots & \ddots &\ddots & \vdots \\ \lambda & \lambda &\cdots & \cdots & k\end{pmatrix}$$

The $i$-th diagonal entry of this matrix which is equal to $k$, is just the dot product between the $i$-th row of $X$ and $i$-th column of $Y$,  both according to the problem with total sum $k$ and $k+1$. 

From this we can deduce that the $i$ -th column of $Y$ is just a nearly exact copy of $i$-th row of $X$, they only differ in one non-zero entry, let's call these entries speciality .  

If we separate these so called specialities into a separated matrix $P$, we will get

$$Y = X^T + P$$

where $P$ contains the separated specialities.  Furthermore, $P$ is a permutation matrix, namely there is exactly single $1$ on each column  and exactly single $1$ on each row  (since otherwise $Y$ would have a row/column with total sum greater than $k+1$)

Now,  we can make $P$ into an identity matrix by right-multiplying $Y$ with some permutation matrices, recall that the right-multiplication of a matrix with permutation matrix will permute the column of the given matrix, while the left multiplication will permute the row.  

So choosing permutation matrices $\mathcal{P} = P_1 P_2  \cdots P_m$ where each $P_i$ is a transposition (i.e obtained by interchanging two columns of identity matrix) we make $P \mathcal{P} = I$.  

This make $Y$ into $B = X^T  \mathcal{P} + I = (\mathcal{P}^T X)^T + I$ 

Observe that $\mathcal{P}^T = P_m^T P_{m-1}^T \cdots P_1^T = P_m P_{m-1} \cdots P_1$ , since each transposition is symmetric.  

Putting $A=(P_m P_{m-1} \cdots P_1 X)$, we see that $A$ is just a row permuted from $X$, and so the condition of  line-sum equals $k$ is still intact. Furthermore, we also make all diagonal entries of $A$ become zero, since by moving those specialities on $Y$ into diagonal, we also moving the respective zeros related to the speciality into the diagonal of $X$. 

$$A (A^T + I) = P_m P_{m-1} \cdots P_1 (H(k,\lambda)) P_1 P_2 \cdots P_m$$

but $P_m P_{m-1} \cdots P_1(H(k,\lambda)) P_1 P_2 \cdots P_m = H(k, \lambda)$, this because if we interchange the $i$-th column  and  the $j$-th column of $H(k,\lambda)$  and then interchange $i$-th row and $j$-th row, we will back again to $H(k, \lambda)$.  

So we have equation

$$AA^T+A = H(k,\lambda)$$

Taking the transpose of both sides we have $A^T = A$, and so the equation becomes $A^2+A = H(k, \lambda)$, with $trace(A)=0$ and line-sums of $A$ is all $k$. 

Now being a symmetric matrix, $A$ is (orthogonally) diagonalizable, and we can transform the above equation into

$$D^2 + D = W$$

where $D$ is diagonal matrix which consists eigenvalues of $A$, and diagonal matrix $W$ which consists the eigenvalues of  $H(k, \lambda)$.

The eigenvalues of $H(k,\lambda)$ are easy too obtain, indeed, by simple calculation we may check that $(1,-1, 0, 0, ... , 0)^T$, $(0,1,-1, 0, ..., 0)^T$, ..., $(0,0,0,0..., 1, -1)^T$, and $(1,1,1,...,1)^T$ are linearly independent eigenvectors of  $H(k, \lambda)$ with eigenvalues $\underbrace{k-\lambda, k-\lambda, ..., k-\lambda}_{k \, many}$ and $k+\lambda(n-1)$, respectively.

The eigenvalues of $A$, is less trivial, observe that since row sum of $A$ is $k$, we know that $k$ is an eigenvalue of $A$ with eigenvector $(1,1,1,1,...,1)^T$. 

Let say the (multi)-set of eigenvalue of $A$ is $\sigma(A)= \{k, l_1, l_2, ... , l_{n-1}\}$ (sometime called spectrum of $A$), so $\sigma(D^2+D) = \{k^2+k , l_1^2+l_1, ... , l_{n-1}^2+l_{n-1}\}$ we must have

$$\{k^2+k , l_1^2+l_1, ... , l_{n-1}^2+l_{n-1}\} = \{k-\lambda, k-\lambda, ..., k-\lambda , k+(n-1)\lambda\}$$

Let start with $k^2+k$, if $k^2+k=k-\lambda$, we will have $k^2=-\lambda$, this can't be right since $\lambda$ is non-negative and $k$ is non-zero.  So we must have $k^2+k = k+(n-1)\lambda$, and we have

$$k^2= (n-1) \lambda$$

Now then we also have $l_i^2+l_i = k-\lambda$, thus we get

$$l_i = \frac{-1+\sqrt{1+4(k-\lambda) }}{2} \qquad \text{or} \qquad l_i= \frac{-1-\sqrt{1+4(k-\lambda) }}{2}$$

But since  $1+4(k-\lambda)$ is not a square $l_i$ is irrational number. But from $trace(A)=0$ we also have 

$$k+l_1 + l_2 + ...  + l_n = 0$$

so the sum of these irrational numbers is an integer, thus they must occurs in conjugate pairs. It means that exactly $\frac{n-1}{2}$ of $l_i$ is $\frac{-1+\sqrt{1+4(k-\lambda) }}{2}$ while the other $\frac{n-1}{2}$ is $\frac{-1-\sqrt{1+4(k-\lambda) }}{2}$. 

Now each conjugate pairs summed to $-1$, so we must have $l_1 + l_2 + ... + l_{n-1} = -\frac{(n-1)}{2}$.  Therefore

$$k-\frac{n-1}{2}=0 \Rightarrow n=2k+1$$

Substituting this into $k^2=(n-1)\lambda$ we will get $k=2\lambda$, furthermore back substitution will yield $n=4\lambda +1$, and we are done. 

Update: I typed a quite-long formally written proof in this pdf file.

ShareShare on Facebook

TweetShare on Twitter

Pin ItShare on Pinterest