Everything over F\_2. 


For any matrix $A$ define the number $N(A) = min\_{x}$ [HammingWeight](http://en.wikipedia.org/wiki/Hamming_weight) $( [x , Ax])$.
Where $x$ is vector and [a,b] is just concatenation of vectors: (a\_1,...a\_n, b\_1,...,b\_m).


**Question** What is $max\_{A \in Mat(n,m) } (N(A))$ ? 


Particular case n=m. 




---


Motivation.


The map $x \to [x, Ax] $ can be considered as error-correcting coding,
$x$ - information bits, $Ax$ are redundancy bits.


The code is good if distance between codewords is small.


Reformulation of question: what is the "best possible" code of type above ? ("best possible" in the sense
of minimal distance -- it is not always "best" from practical point of view nevertheless).



What is  matrix A such that Hamming weight of [x, Ax] is maximal ? (Min distance of 1/2 block code?)
This is, indeed, an open question for most values of $n$. A.D. Brouwer maintains a database of the best known lower
and upper bounds, and everything that is known for small $n$ can be found there. A minute of googling points me at 


<http://mint.sbg.ac.at/desc_CBrouwerTable-Bound.html>


Asymptotically the best bound is usually the linear programming bound due to McEliece-Rodemich-Rumsey and Welch, but the asymptotic bounds may not be very good for rate 1/2 codes.


An interesting simple general existence proof is described in van Lint's book (Springer GTM series).
Fix a basis for $F=GF(2^n)$. Treat $x$ as an element of $F$, and use encoding $x\mapsto (x,ax)$, where $a$ is an element of $F$ that we choose carefully. Fix a target minimum distance. Let $S(i)$ be the set of elements of $F$ of weight $i$, so $|S(i)|={n\choose i}.$ We must disallow all those elements $a$ that can be written in the form $a=y/x$, where
$x\in S(i), y\in S(j), i+j\lt d$. The number of disallowed elements $a$ is thus at most
$$
N(d)=\sum\_{0\lt i,j\lt d; i+j\lt d}{n\choose i}{n\choose j}.
$$
If $N(d)\lt 2^n$ we have not disallowed all the elements of $F$, so the construction succeeds.


