Combinatorial problem using vector space Let me state the problem first. This is an exercise from discrete math.
Let $k$, $n$ be positive integers with $1 \leq k \leq n$. Let $\mathcal{F} = \{A_1,A_2, \cdots, A_m\}$ be a set of subsets of $\{1,2,\cdots,n\}$, such that $|A_i \cap A_j| = k$ for all $i \neq j$. What I want to show is $m \leq n$.
The problem suggests the way:
First, define $m$ vectors $v_1,v_2, \cdots, v_m \in \mathbb{R}^n$, as  $(\text{$j$th coordinate of $v_i$}) = 1 \text{ if } j \in A_i \text{ and } 0 \text{ else}$. And show that $\{v_1,v_2, \cdots, v_m\}$ are linearly independent.
If I was able to prove that, then the result is immediate since $\mathbb{R}^n$ has a basis of size $n$, so $m \leq n$ from the fact that basis is maximal linearly independent subset.
However, I have no idea how to tackle it. How can I use the property $|A_i \cap A_j| = k$ to prove their linear independence? This is definitely a combinatorial problem, but the problem suggests (a seemingly very effective) approach using vector space.
Thank you for any form of help, hint, or solution.
 A: (There must be a simpler way of doing this.)
Let's first consider a couple of slightly annoying cases. First, suppose that $m = 1$. Then obviously $m \le n$, as $n \ge 1$, from our assumption (even though we could have $A_1 = \emptyset$, which would spoil the hint).
Less trivially, suppose $|A_j| = k$ for some $j$. Then $A_j$ contains its intersection with each other $A_i$, but both sets have the same number of elements. From this, we conclude that $A_j = A_j \cap A_i \subseteq A_i$. So, $A_j$ is the $k$ element intersection between any two distinct sets.
If this is the case, the sets $B_i = A_i \setminus A_j$ form a set of pairwise disjoint subsets of $\{1, 2, \ldots, n\} \setminus A_j$, which contains $n - k$ points. This means we can have at most $n - k + 1 \le n$ (don't forget $B_j = \emptyset$) different $B_i$s, with the optimal solution involving each $B_i$ being a singleton.
So, we assume each $|A_i|$ is not equal to $k$. As $m > 1$, we see that each $A_i$ must contain at least a $k$ element intersection with a different $A_j$, so $|A_i| > k$ for all $i$.
Consider the Gramian matrix $G$ of $v_1, \ldots, v_m$ (which is just $A^\top A$ where $A$ is the matrix formed by taking $v_1, \ldots, v_m$ as columns). This matrix is invertible if and only if $v_1, \ldots, v_m$ is independent.
The entry $G_{ij}$, in the $i$th row and $j$th column, is the dot product of $v_i$ with $v_j$. In this case, we have that $G_{ij} = k$ for $i \neq j$. Otherwise, $G_{ii} = \|v_i\|^2$ is the number of non-zero entries in $v_i$, i.e. $|A_i|$. That is,
$$G = \begin{pmatrix}
|A_1| & k & k & \cdots & k \\
k & |A_2| & k & \cdots & k \\
k & k & |A_3| & \cdots & k \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
k & k & k & \cdots & |A_m|
\end{pmatrix}.$$
This is where it is helpful to have $|A_i| > k$ for all $i$. We can now express $G$ as the sum:
$$G = \begin{pmatrix}
k & k & k & \cdots & k \\
k & k & k & \cdots & k \\
k & k & k & \cdots & k \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
k & k & k & \cdots & k
\end{pmatrix} + \begin{pmatrix}
|A_1| - k & 0 & 0 & \cdots & 0 \\
0 & |A_2| - k & 0 & \cdots & 0 \\
0 & 0 & |A_3| - k & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & |A_m| - k
\end{pmatrix}.$$
The former is positive-semidefinite (call the matrix $B$, and observe it is a positive multiple of $B^\top B$, which is automatically positive-semidefinite) and the latter is positive definite, as it is a diagonal matrix with strictly positive diagonal entries. Their sum is positive-definite. In particular, $G$ is invertible, hence $v_1, \ldots, v_m$ is linearly independent.
A: If $m=1$ then $m\le n$ is immediate, so assume $m > 1$.

Also assume $A_1,...,A_m$ are distinct.

Necessarily we have $|A_i|\ge k$ for all $i$.

Consider two cases . . .

Case $(1)$:$\;|A_i|=k$ for some $i$.

Relabeling if necessary, assume $|A_m|=k$.

It follows that $A_m$ is a proper subset of $A_i$ for all $i\in\{1,...,m-1\}$.

For each $i\in\{1,...,m-1\}$, let $B_i=A_i{\setminus}A_m$.

Then we have

*

*Each $B_i$ is nonempty.$\\[4pt]$

*$B_1,...,B_{m-1},A_m$ are pairwise disjoint.

hence
$$
m\le (m-1)+k
\le
|B_1\cup\cdots\cup B_{m-1}\cup A_m|\le |\{1,...,n\}|=n
$$
which resolves case $(1)$.

Case $(2)$:$\;|A_i| > k$ for all $i$.

Then $v_i^2 > k$ for all $i$.

Now suppose that $v_1,...,v_m$ are linearly dependent.

Our goal is to derive a contradiction.

Let $a_1,...,a_m\in\mathbb{R}$, not all zero, be such that
$$
a_1v_1+\cdots +a_mv_m=0
$$
and let $s=a_1+\cdots +a_m$.
\begin{align*}
\text{Then}\;\;&
a_1v_1+\cdots +a_mv_m=0
\\[4pt]
\implies\;&
a_iv_i{\,\cdot\,}(a_1v_1+\cdots +a_mv_m)=0,\;\text{for all $i$}
\\[4pt]
\implies\;&
a_i(s-a_i)k+a_i^2v_i^2=0,\;\text{for all $i$}
\\[4pt]
\implies\;&
\sum_{i=1}^m a_i(s-a_i)k+a_i^2v_i^2=0
\\[4pt]
\implies\;&
\sum_{i=1}^m a_i(s-a_i)k+\sum_{i=1}^m a_i^2v_i^2=0
\\[4pt]
\implies\;&
\sum_{i=1}^m a_i(s-a_i)k+\sum_{i=1}^m ka_i^2 < 0
\\[4pt]
\implies\;&
\sum_{i=1}^m a_i(s-a_i)k+ka_i^2 < 0
\\[4pt]
\implies\;&
\sum_{i=1}^m ksa_i < 0
\\[4pt]
\implies\;&
ks\sum_{i=1}^m a_i < 0
\\[4pt]
\implies\;&
ks^2 < 0
\\[4pt]
\implies\;&
s^2 < 0
\\[4pt]
\end{align*}
contradiction, which resolves case $(2)$.

This completes the proof.
A: If all $|A_i|$ are odd and $k$ is even and we work in $Z_2$ instead of $R$ then write $$ s_1v_1+...s_mv_m=0$$ for some scalars $s_1,s_2,...$
Clearly $v_i\cdot v_j=0$ if $i\ne j$ and $1$ if $i=j$. Now multiply that equation with $v_1$ and you get $$s_1\cdot 1 + 0+...+0=0$$ so $s_1 =0$ and simillary for other inidices, so $v_1,v_2...$ are lineary independent and we are done.
Anyway, you can find general result here: Fisher's inequality
