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".

  • 2
    $\begingroup$ 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). $\endgroup$ – Chris Godsil Feb 27 '12 at 13:35
  • $\begingroup$ @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... $\endgroup$ – Alexander Chervov Feb 27 '12 at 13:52

Your Answer

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

Browse other questions tagged or ask your own question.