Exists a non-empty subset $K$ of $2005$ senators in senat such that for every senator, the number of his enemies in $K$ is an even number. 
There are $2005$ senators in a senate. Each senator has enemies within the senate. Prove that there exists a non-empty subset $K$ of senators such that for every senator in the senate, the number of his enemies in $K$ is an even number.

Let $n=2005$ and let $s_i$ be an indicator vector for $i$-th senator. So we are working in $\mathbb{F}_2^n$ and we are looking for such a vector $u$ that $s_i\cdot u =0$ for all $i$.
Now we can make a matrix $M = [s_1,...,s_n]$ which is symmetric and thus it has $\det M =0$ since $n$ is odd. So it has nontrivial kernel so there exists $u\ne 0$ such that $Mu=0$. Clearly $u$ is a vector we are looking for and thus we are done.

Now, I wonder if it can be done without matrix theory, only in terms of linear independence and ''similar things''from linear algebra. My idea was to put $S := \langle s_1,s_2,...,s_n \rangle$ and prove that $S^{\bot} $ is nontrivial, which would be true if $s_1,s_2,...,s_n$ are lineary dependent.
All I can think is that by handshake lemma and since $n$ is odd, at least one senator has even number of enemies. Suppose it is $s_1$, so if $s_1\cdot s_j =0$ for all $j>1$ we are done. But what if that is not the case.
 A: Here is a possibility to "not use matrices, but linear algebra". (Bilinear forms, and use "symplectic" ideas.)
Let $n$ be an odd positive integer. Let $F$ be the field with two elements and $V=F^n$ the canonical vector space of dimension $n$ over $F$. (Elements are identified with column vectors with $n$ components in $F$.)
Let $e_1, e_2,\dots,e_n$ be the canonical basis of $V$.
Let $e_I$ be $\displaystyle e_I=\sum_{i\in I}e_i$ for some subset $I$ of the index set $\{1,2,\dots,n\}$. Each element of $V$ is of the shape $e_I$ for a suitable $I$.
Let $B$ be the symmetric bilinear form so that
$B(e_i,e_j)$ is the $j$'th component in $s_i$ and/or the $i$'th component in $s_j$.
(Comment: The associated matrix $S$ for this bilinear form is the matrix with columns $s_1,\dots,s_n$, and $B(v,w)=v'Sw$. Note that it is essential that no senator feels to be its own enemy, translated by the fact that the diagonal entries in $S$ are all zero. The OP should have mentioned this in the row that claims $\det S=0$. This comment is not part of the solution, we will tacitly use $B(e_i, e_i)=0$, equivalent to $S_{ii}$=0, a relation which is valid for all $i$.)
Assume that this bilinear form is non-degenerated.
(We try to develop a contradiction.)
This form is not only skew-symmetric (since it is symmetric, and we are in characteristic two), but also alternating:
$$
B(e_I,e_I)
=\sum_{i,j\in I}B(e_i, e_j)
=\sum_{i\in I}B(e_i, e_i) 
+2
\sum_{\substack{i,j\in I\\i<j}}B(e_i, e_j)
=0\ .
$$
An alternating $B$ can live only in even dimension. Contradiction.
So $B$ has non-trivial kernel.
(From the degeneration, we obtain a non-zero $v\in V$ in the kernel of the canonical map $V\to V^*$ induced by $B$, so $w\to B(w,v)=w'Sv$ is the zero map in $V^*$, so $Sv$ is the zero vector.)
$\square$

Here is the argument involved (induction with step two on $n=\dim V$) for the even dimension above. ("Not using matrices", it is the usual argument, mentioned explicitly to show that the idea can be accepted in the thematic of the OP, passing to the orthogonal space is used for instance.)
Let $B$ be alternating, non-degenerated on $V$. If $\dim V=0$ there is nothing to show. If $\dim V=1$ then it has only one non-zero vector $v\in V\cong\Bbb F_2$, and from $B(v,v)=0$ we obtain $B=0$, contradiction. So the needed property holds for all vector spaces with dimension $<2$. Let $V$ be a space of dimension $\ge 2$ now. There is some $u\in V$, $u\ne 0$. Since $B(u,u)=0$, but $B(u,\cdot)\not \equiv 0$, there is some $v\in V$ with $B(u,v)=1$.
Consider now the subspace $U=\langle u,v\rangle$, and its orthogonal complement w.r.t. $B$,
$$
\tag{$\dagger$}
W=U^\perp\ .
$$
Then standard arguments show that $V=U\oplus W$, and consider for the inductive step the restiction of $B$ to $W$, again alternating and non-degenerated.
(Explicitly, and without matrices: Since $B$ is non-degenerated, $U\cap W=U\cap U^\perp=0$, since none of the only non-zero elements of $U$, enumerated as $u$, $v$, $u+v$, lies in $U^\perp$. We further need the property $U+U^\perp=V$. Consider for this the map into the dual $U\to U^*$, $y\to B(y,\cdot)\Big|_U$, given explicitly by
$0\to 0$, $u\to B(u,\cdot)\Big|_U$, $v\to B(v,\cdot)\Big|_U$, $u+v\to B(u+v,\cdot)\Big|_U$. It is injective, thus surjective, so an isomorphism of linear spaces of dimension two.
Then for each $x\in V$ the form $B(x,\cdot)\Big|_U$ can be realized with an element $y\in U$. So $B(x-y,y')=0$ for all $y'\in U$. This means $x-y\in U^\perp = W$, realizing $x\in y+W\subset U+W$.)

Note: A matrix $M$ as the given one is exactly a matrix for an alternating bilinear form.
