Library linear algebra Problem!

177 Views Asked by At

This is a problem which for me is a little difficult to give a concrete result:

In a school , there are $n+1$ students and $n$ books in a school library. Suppose that every student has read at least one book. Prove that there exist two mutually disjoint non empty sets $A$ and $B$ of students such that for any book in the library, the book has been read by at least one student from set $A$ if and only if it also has been read by at least one student from set $B$.

My idea is to assume we are working in a vector space of $n\times (n+1)$ matrices and suppose there's a non-zero solution $X = (x_1,...,x_n)$ and let: $A = \{i: x_i >0\}$ $B = \{j: x_j <0\}$

The thing is that I don't know how to prove there at least one student in $A$ that read a book iff there a student in $B$ that also read that book.

1

There are 1 best solutions below

0
On BEST ANSWER

Number the books $1,\dots, n$ and the children $1,\dots, n+1$. Let $M$ be the $n \times (n+1)$ matrix that stores all the information about the books and children: the entry in row $i$ and column $j$ is a 1 if child $j$ has read book $i$, otherwise 0. Since $M$ is the matrix of a linear transformation from $\mathbb{R}^{n+1}$ to $\mathbb{R}^n$, it has a null space of nonzero dimension. Thus there exists some $x \neq 0$ such that $Mx = 0$.

Let the components of $x$ be $x_j$, where $j=1,\dots, n+1$. As you say, set $A = \{j: x_j > 0\}$ and $B = \{j: x_j < 0\}$. Clearly $A$ and $B$ are disjoint.

For any $j \in A$, suppose child $j$ has read book $i$. Focus on the $i^\text{th}$ row of $Mx$: $$ M_{i1} x_1 + \cdots + M_{ij} x_j + \cdots + M_{i,n+1} x_{n+1} = 0 $$ Since all the $M_{ik}$ are nonnegative and $M_{ij} x_j$ is positive and this expression sums to $0$, there must be some $k$ such that $M_{ik} x_k$ is negative, meaning $x_k$ is negative and child $k$ has read book $i$. That is, there is a $k \in B$ that has read book $i$.

The same argument works the other way around, showing that the books read by children in $A$ and children in $B$ are the same.