# My fun conjecture about linearly independence

In the $\mathbb{R}^n$ vector space, there are distinct $m$ vectors $v_i$'s ($1< i\leq m)$ such that each component has value 0 or 1.

Let $A_i$ be the set of $j$'s where $j$-th component of $v_i$ is 1.

Also, for each $i \neq j$, $A_i$ and $A_j$ has common $k$ elements. Where $k$ is a given integer $1\leq k <n$.

For example, when $n=3, k=1$. $v_1=(1,1,0), v_2=(1,0,1), v_3=(0,1,1)$ satisfy those conditions since $A_1=\{1,2\},A_2=\{1,3\},A_3=\{2,3\}$.

My conjecture is : those $v_i$'s are linearly independent.

With some rough programming, this conjecture was true when $n \leq 10$.

I tried to prove this conjecture with induction on $k$, but I failed.

*Some people misunderstood question.

Actually question is : For given $n,m,k$, is every families of vectors with above condition are linearly independent.

Can you prove or disprove this conjectrue?

• $(1,0), (0,1), (1,1)$ are linearly dependent but seem to satisfy your description. – lhf Jul 1 '14 at 11:48
• @lhf (1,0) and (0,1) has no common elements but other pair has 1 common elements – Maddy Jul 1 '14 at 11:49
• As I have understood it, your conjecture says that given $k$, if a subset $V$ of $B=\{$ vectors whose components are 0 or 1$\}$ satisfies the property of that for each pair of vectors in $V$, the number of 1-components that have in common is $k$, then $V$ is l.i. Is it correct? – ajotatxe Jul 1 '14 at 12:02
• Hmm, so if there is some $j$ for which precisely one of the vectors has a $1$ in the $j$'th position, then one can safely remove that and proceed by induction on $m$. I am not sure if this leads anywhere though. – Tobias Kildetoft Jul 1 '14 at 12:08
• You have to restrict $k > 0$. Otherwise, $0$ and $1$ satisfy the description, but are trivially dependent. Also, you need $m > 1$ because any single-element set trivially satisfies the conditions, but a set containing only $0$ is not linearly independent. – Vedran Šego Jul 1 '14 at 12:43

Your condition says that $\langle v_i,v_j\rangle = k$ when $i\ne j$, and let's write $\langle v_i,v_i\rangle = n_i$. Let $A$ be the matrix having the $v_i$ as columns. Then
$$A^TA = \begin{pmatrix}n_1 & k & k & \cdots & k \\ k & n_2 & k & \cdots & k \\ & & \ddots & & \\ k & k & k & \cdots & n_m \end{pmatrix}$$
Note that at most one of the $n_i$ can be equal to $k$ because any two of them would have to be equal. Also note that we have to explicitly exclude the case that $v_i = 0$ for some $i$. Otherwise we are done: $A^TA$ is clearly invertible so $A$ can not have a non-trivial kernel, i.e. no non-trivial linear combination of its columns, the $v_i$, can give $0$.