4
$\begingroup$

We are given a list of 23 subsets, each with an odd number of elements such that any two subsets have an even number of elements in common. There are 26 elements in the set. Prove that you can add a new subset with an odd number of elements that has even number of elements with each of the other subsets.

Proof: Let $\vec{v}_1,\vec{v}_2,...\vec{v}_{23}$ be a characteristic (indicator) vectors for given sets. So we have 23 vectors in $\mathbb{Z}_2^{26}$ such that $\vec{v}_i^2 =1$ and $\vec{v}_i\cdot \vec{v}_j =0$ for each $i\ne j$. Clearly they are independent so $V:=$span $\{\vec{v}_1,\vec{v}_2,...\vec{v}_{23}\}$ has dimension $23$. Let $\{\vec{u}_1,\vec{u}_2,\vec{u}_3\}$ be a basis for $V^{\bot}$. Then clearly $u_i\cdot v_j = 0$ and we have to prove that for at least one $i$ we have $u^2_i=1$. Suppose we have $u^2_i=0$ for each $i$.

Let $\vec{1} = (1,1,. . . 1)$ then we have some scalars $m_1, m_2,. . . m_{23}, n_1, n_2, n_3$ such that $$\vec{1} = m_1\vec{v}_1 + m_2\vec{v}_2 + . . . + n_3\vec{u}_3$$

By multiplying this equation with each $\vec{v}_i$ we get $m_1=m_2 = ...= m_{23}=1$, and if we multiply it with $\vec{1} $ we get $$ 0 = 1+1+...+1+n_1\cdot 0 + n_2\cdot 0 +n_3\cdot 0 = 1$$ wich is a nosense, so we are done.

Is this proof correct?

$\endgroup$
4
  • 2
    $\begingroup$ Why must the characteristic (indicator) vectors be independent? $\endgroup$ Commented Sep 18, 2020 at 20:54
  • 1
    $\begingroup$ Aqua, I suggest you ignore the above comment; your proof is correct and well-written. The only minor thing I would suggest is to remove "not all zero" -- it is of course true, since the left hand side is $\vec{1}$, but I'm really not sure why you're saying it, and think you are saying it for an invalid reason. $\endgroup$ Commented Sep 18, 2020 at 21:54
  • $\begingroup$ As always, sharp look. Thanks @mathworker21 I'm not sure if $\{v_1,....,u_3\}$ constitue a basis for whole space. Is it walid for finite dimensonal space $U$ that $U = V\oplus V^{\bot}$? It sims pretty obviously, but not sure. $\endgroup$
    – nonuser
    Commented Sep 19, 2020 at 7:30
  • $\begingroup$ @Aqua Yes, it's true. Here's a proof (I think). All finite dimensional vector space stuff is isomorphic to $\mathbb{R}^n$, so we can pretend everything is happening in $\mathbb{R}^n$. And then I think it's pretty obvious. I think, for any finite dimensional subspace $V$ of $\mathbb{R}^n$, we can do a linear transformation to make a given basis of $V$ become $e_1,\dots,e_k$, where $\dim(V) = k$ and $e_i = (0,\dots,0,1,0,\dots,0)$, where the $1$ is in position $i$. Then $V^{\perp}$ has basis $e_{k+1},\dots,e_n$, and clearly $\mathbb{R}^n = V\oplus V^\perp$. $\endgroup$ Commented Sep 19, 2020 at 8:54

1 Answer 1

1
+50
$\begingroup$

I think your proof is correct.

To address concerns in the comments:

$(1)$ Independence of $v_i$'s

Let $$\sum_{i=1}^{23} c_i v_i = 0 \tag 1$$

be a relation such that not all the $c_i$ are $0$. Let $c_r$ be the first nonzero coefficient. Right multiplying $(1)$ by $v_r$ gives

$$c_r v_r^2 = 0 \implies c_r \cdot 1 = 0 \implies c_r = 0$$

which is a contradiction.

I guess people were concerned because normally the multiplication you define causes problems with the above proof over finite fields: e.g., what if $v_i^2 = 0$, as in $v_i = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$ over $\mathbb{Z}/2\mathbb{Z}$. But this doesn't happen in your case.

$(2)$ Is $\{v_1,...,v_{23},u_1,u_2,u_3\}$ a basis? (Yes)

The multiplication you define is a bilinear form so you can talk about its orthogonal complement. Since it is a non-degenerate bilinear form, we know that dim $(W) \ + $ dim $(W^\perp) = $ dim $\mathbb{Z}_2^{26}$ (see Wikipedia for more information).

So we can find three independent $u_i$ in the orthogonal complement as you suppose. Now we need only show that all of these vectors are independent and we are done.

Let $$\sum_{i=1}^{23} c_i v_i + \sum_{i=1}^{3} d_i u_i = 0 \tag 2$$

be a relation such that not all the $c_i$ and $d_i$ are $0$. Let $c_r$ be the first nonzero coefficient among the $c_i$'s. Right multiplying $(2)$ by $v_r$ again gives $c_r = 0$. So $c_1 = \cdots = c_{23} = 0$.

Therefore $(2)$ becomes

$$\sum_{i=1}^{3} d_i u_i = 0 \tag 3$$

But the $u_i$ are independent so we have $d_1 = d_2 = d_3 = 0$, as desired.

$\endgroup$
1
  • $\begingroup$ Ah yes, I missed last part. Great, thanks! Do you now any high school combinatorics or number theory problem that can be solved using LA like this one? $\endgroup$
    – nonuser
    Commented Sep 19, 2020 at 17:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .