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?

  • $\begingroup$ $(1,0), (0,1), (1,1)$ are linearly dependent but seem to satisfy your description. $\endgroup$ – lhf Jul 1 '14 at 11:48
  • $\begingroup$ @lhf (1,0) and (0,1) has no common elements but other pair has 1 common elements $\endgroup$ – Maddy Jul 1 '14 at 11:49
  • 1
    $\begingroup$ 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? $\endgroup$ – ajotatxe Jul 1 '14 at 12:02
  • $\begingroup$ 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. $\endgroup$ – Tobias Kildetoft Jul 1 '14 at 12:08
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.