MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider bipartite graph. Consider its adjacency matrix. It will have a form

0 A^t

A 0

Take matrix $A$. Consider the null-space $L$ of $A$ over $F_2^N$.

Question Can we say something about the $L$ from graph theoretic perspective ? For example to determine what is minimum Hamming weight for vectors in $L$ ?

In error correction codes community the following words are used: Original graph is called Tanner graph for $A$. Matrix $A$ is called parity-check matrix. Let dim(L)=k, any linear map $F_2^k \to L\subset F_2^N$ is called "encoder".

share|cite|improve this question
What you have called the incidence matrix is actually the adjacency matrix (as will be clear if you read the article you've linked to). Your approach translates all coding theory questions into graph theory questions. It seems unlikely that much will be gained by the translation. Of course there are many papers studying the case when $A$ is sparse (LDPC codes). – Chris Godsil Feb 27 '12 at 13:35
@Chris Thank You, I corrected ! Shame on me I am always mixing these matrices. Fields medalist G. Margulis constructed some "good" LDPC codes by Cayley graphs (???) of some groups GL(F,p) - as I heard but not really understand. There are lots of papers about "expanders" graphs which is probably related to this question... I just start learning these things so, may be question is not really good... – Alexander Chervov Feb 27 '12 at 13:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.