ISSN 2148-838Xhttps://doi.org/10.13069/jacodesmath.1111379 J. Algebra Comb. Discrete Appl. 9(2) • 79–84 Received: 14 September 2021 Accepted: 6 January 2022 Journal of Algebra Combinatorics Discrete Structures and Applications A new formula for the minimum distance of an expander code Research Article Sudipta Mallik Abstract: An expander code is a binary linear code whose parity-check matrix is the bi-adjacency matrix of a bipartite expander graph. We provide a new formula for the minimum distance of such codes. We also provide a new proof of the result that 2(1 − ε)γn is a lower bound of the minimum distance of the expander code given by an (m,n,d,γ,1 − ε) expander bipartite graph. 2010 MSC: 94B05, 94B25 Keywords: Linear code, Minimum distance, Expander graph, Adjacency matrix 1. Introduction Binary linear codes can be constructed from graphs. One such construction was given from bipartite graphs by Tanner in [7]. Sipser and Spielman constructed expander codes from bipartite expander graphs in [6]. One of the goals of all these constructions was to have linear codes with relatively large minimum distance for efficient error correction. For more details on the literature of linear codes and bipartite graphs, see [1, 2, 6, 8]. In this article we provide a new formula for the minimum distance of expander codes. We also provide a new proof of the result that 2(1−ε)γn is a lower bound of the minimum distance of the expander code given by an (m,n,d,γ,1−ε) expander bipartite graph. Now we present a brief introduction to coding theory: A binary linear code C of length n and dimension k is a k dimensional subspace of Fn2 where F2 is the binary field. The code C is called an [n,k]-code. The support of a codeword ∈ C is the set of indices i such that ith entry of x is 1. The Hamming weight wH(x) of a vector x ∈ Fn2 is the size of the support of x. The Hamming distance, denoted by dH(x,y), between two codewords x and y in C is dH(x,y) = wH(x − y). The minimum distance of C, denoted by d(C), is the minimum distance between distinct codewords in C. Note that d(C) is the minimum Hamming weight of a nonzero codeword in C. We call C to be an [n,k,d] code when d(C) = d. A binary matrix H is called the parity-check matrix of C if C the null space of H, i.e., C = {c ∈ Fn2 |Hc T = 0}. Sudipta Mallik; Department of Mathematics and Statistics, Northern Arizona University, 801 S. Osborne Dr. PO Box: 5717, Flagstaff, AZ 86011, USA (email: sudipta.mallik@nau.edu). 79 https://orcid.org/0000-0001-7496-2147 S. Mallik / J. Algebra Comb. Discrete Appl. 9(2) (2022) 79–84 1 2 3 4 5 6 7 8 9 L R Figure 1. A ( 5,4,2, 1 2 , 2 3 ) expander graph. The minimum distance d(C) can be expressed as the minimum number of linear dependent columns of the parity-check matrix of C as follows: Theorem 1.1. [5, Theorem 2.2] Let C be a linear code and H its parity-check matrix. Then C has minimum distance d if and only if any d−1 columns of H are linearly independent and some d columns of H are linearly dependent. For a vertex v of a graph G, the set of all vertices in G adjacent to v is called the neighbor of v, denoted by N(v). For a set S of vertices of G, N(S) denotes the union of neighbors of vertices in S. Now we define a bipartite expander graph based on its definition in [6, 7] with the roles of left and right set of vertices switched: Definition 1.2. Suppose G is a bipartite graph with vertex set L∪̇R such that |L| = m, |R| = n, each edge of G joins a vertex of L with a vertex of R, and each vertex of R is adjacent to exactly d vertices of L. For positive γ and α, G is called an (m,n,d,γ,α) expander graph if for each set S ⊆ R satisfying |S| ≤ γn, we have |N(S)| ≥ dα|S|. Example 1.3. The bipartite graph in Figure 1 is a (5,4,2, 1 2 , 2 3 ) expander graph. Each vertex in R has degree d = 2. If S ⊆ R satisfies |S| ≤ γn = 2, then |S| = 1 or 2. For |S| = 1, |N(S)| = 2 ≥ 4 3 = dα|S|. Also for |S| = 2, |N(S)| ≥ 8 3 = dα|S|. Definition 1.4. Suppose G is an (m,n,d,γ,α) expander graph and B is the m×n bi-adjacency matrix of G, i.e., A = [ Om B BT On ] is the adjacency matrix of G. The binary linear code whose parity-check matrix is B is called the expander code of G, denoted by C(G). In other words, C(G) = {c ∈ Fn2 | Bc T = 0 in F2}. 80 S. Mallik / J. Algebra Comb. Discrete Appl. 9(2) (2022) 79–84 Example 1.5. The bi-adjacency matrix of the (5,4,2, 1 2 , 2 3 ) expander graph G in Figure 1 is given by B =   1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0   . The expander code C(G) of G is given by C(G) = {c ∈ F42 | Bc T = 0 in F2}. 2. Main results We start with the following notation and definition of von from [3, 4]. Definition 2.1. For a nonempty subset S of vertices of a graph G, the set of vertices of G with odd number of neighbors in S is denoted by von(S), i.e., von(S) = {v ∈ V (G) : |N(v)∩S| is odd}. Example 2.2. Consider the (5,4,2, 1 2 , 2 3 ) expander graph G in Figure 1. For v = 6,7,8,9, von({v}) = N(v). For S = {6,7,8}, von(S) = {1,3,4,5}. For S = {6,8,9}, von(S) = ∅. Now we proceed to the main results of this article which give a new formula of the minimum distance of an expander code. Theorem 2.3. Suppose G is a bipartite graph with vertex set L∪̇R such that |L| = m, |R| = n, and B is the m×n bi-adjacency matrix of G. Let S be a nonempty subset of R. If von(S) = ∅, then the columns of B indexed by S are linearly dependent. Conversely if the columns of B indexed by S are minimally linearly dependent, then von(S) = ∅. Proof. Suppose von(S) = ∅ where S = {i1, i2, . . . , it}⊆ R. Then Bi1 + Bi2 + · · ·+ Bit ≡ 0 (mod 2) which implies columns Bi1,Bi2, . . . ,Bit of B are linearly dependent. Conversely suppose S = {1,2, . . . ,k} ⊆ R and B1,B2, . . . ,Bk are minimally linearly dependent columns of B. Then B1 + B2 + · · · + Bk ≡ 0 (mod 2). We claim von(S) = ∅. Otherwise let i ∈ von(S). Then (B1 + B2 + · · ·+ Bk)i ≡ 1 (mod 2) , which contradicts B1 + B2 + · · ·+ Bk ≡ 0 (mod 2). Thus von(S) = ∅. Theorem 2.4. Suppose G is a bipartite graph with vertex set L∪̇R such that |L| = m, |R| = n, and B is the m×n bi-adjacency matrix of G. Suppose C is the binary linear code whose parity-check matrix is B. Then the minimum distance d(C) of C is given by d(C) = min{|S| : ∅ 6= S ⊆ R, von(S) = ∅}. Proof. First note that B is the parity-check matrix of C. By Theorem 1.1, the support of a code word in C with weight d(C) is the set of indices of some minimally dependent columns of B, say indexed by T for some nonempty subset T of R. By Theorem 2.3, von(T) = ∅. Then d(C) = |T | ≥ min{|S| : ∅ 6= S ⊆ R, von(S) = ∅}. 81 S. Mallik / J. Algebra Comb. Discrete Appl. 9(2) (2022) 79–84 To show the equality, on the contrary suppose there is a nonempty subset S of R for which d(C) > |S| and von(S) = ∅. Then by Theorem 2.3, we find |S| linearly dependent columns of B giving a codeword of C with weight less than d(C), a contradiction. Example 2.5. Consider the (5,4,2, 1 2 , 2 3 ) expander graph G in Figure 1. Suppose C is the binary linear code whose parity-check matrix is the bi-adjacency matrix of G. We can verify that for any nonempty set S ⊆ R with |S| ≤ 2, we have von(S) 6= ∅. Now for S = {6,8,9}, von(S) = ∅. Thus by Theorem 2.4, d(C) = min{|S| : ∅ 6= S ⊆ R, von(S) = ∅} = |{6,8,9}| = 3. The preceding theorem results in a new formula for the minimum distance of expander codes. Theorem 2.6. Suppose G is an (m,n,d,γ,α) expander graph with vertex set L∪̇R such that |L| = m and |R| = n. Then the minimum distance d(C) of the expander code C of G is given by d(C) = min{|S| : ∅ 6= S ⊆ R, von(S) = ∅}. Using the minimum distance formula given in Theorem 2.6, we provide a new proof of the following known result which gives a lower bound of the minimum distance of an expander code. Theorem 2.7. Let 0 < ε < 1 2 and γ > 0 such that γn is a positive integer. Suppose G is an (m,n,d,γ,1− ε) expander graph with vertex set L∪̇R such that |L| = m and |R| = n. Then the minimum distance d(C) of the expander code C of G has the following lower bound: d(C) ≥ 2(1−ε)γn. To prove Theorem 2.7, we first prove the following lemmas: Lemma 2.8. Let 0 < ε < 1 2 . Suppose G is an (m,n,d,γ,1−ε) expander graph with vertex set L∪̇R such that |L| = m and |R| = n. For each set S ⊆ R satisfying |S| ≤ γn, we have d(1−2ε)|S| ≤ |von(S)| ≤ |N(S)|. Proof. Suppose S ⊆ R satisfies |S| ≤ γn. The second inequality follows from the fact von(S) ⊆ N(S) ⊆ L by definition. To show the first inequality, note that there are d|S| edges between vertices in S and vertices in N(S) ⊆ L and each vertex in von(S) has at least one neighbor in S. Also each vertex in N(S)\von(S) has even number (at least 2) of neighbors in S. Thus d|S| ≥ |von(S)|+ 2|N(S)\von(S)| = 2|N(S)|− |von(S)| which implies |von(S)| ≥ 2|N(S)|−d|S|. Since |S| ≤ γn and G is an (m,n,d,γ,1−ε) expander graph, |N(S)| ≥ d(1−ε)|S|. Thus |von(S)| ≥ 2|N(S)|−d|S| ≥ 2d(1−ε)|S|−d|S| = d(1−2ε)|S|. Lemma 2.9. Suppose G is a bipartite graph with vertex set L∪̇R. Let A and B be nonempty disjoint subsets of S ⊆ R such that S = A∪B. If von(S) = ∅, then von(A) = von(B). Proof. Let von(S) = ∅. To show von(A) ⊆ von(B), suppose x ∈ von(A). We claim x ∈ von(B). Otherwise x /∈ von(B), i.e., x is adjacent to an even number of vertices in B. Since x ∈ von(A), x is adjacent to an odd number of vertices in A. Thus x is adjacent to an odd number of vertices in S = A∪B. Therefore von(S) 6= ∅, a contradiction. Thus von(A) ⊆ von(B). Similarly we can show that von(B) ⊆ von(A). 82 S. Mallik / J. Algebra Comb. Discrete Appl. 9(2) (2022) 79–84 Using the above lemmas, we prove Theorem 2.7. Proof of Theorem 2.7. By Theorem 2.6, consider a nonempty set S ⊆ R such that d(C) = |S| and von(S) = ∅. To prove by contradiction, suppose 2(1−ε)γn > d(C) = |S|. Case 1. |S| ≤ γn By Lemma 2.8, d(1−2ε)|S| ≤ |von(S)|. Since ε < 1 2 , we have 0 < d(1−2ε)|S| ≤ |von(S)|, which implies von(S) 6= ∅, a contradiction. Case 2. |S| > γn In this case 2(1−ε)γn > |S| > γn. Choose a nonempty subset T of S ⊆ R such that |T | = γn. Then by Lemma 2.8, d(1−2ε)γn = d(1−2ε)|T| ≤ |von(T)| ≤ |N(T)|. (1) Note that |S \T| = |S|− |T | < 2(1−ε)γn−γn = (1−2ε)γn. Since each vertex in S \T has d neighbors in L, by Lemma 2.8, |von(S \T)| ≤ |N(S \T)| ≤ d|S \T | < d(1−2ε)γn. (2) Combining (1) and (2), we have |von(S \T)| < d(1−2ε)γn ≤ |von(T)|, which implies von(S \ T) 6= von(T). Since S = S ∪ (S \ T) and von(S) = ∅, by Lemma 2.9, we have von(S \T) = von(T), a contradiction. Observation 2.10. If we like to find the minimum distance d(C) of the expander code C of an (m,n,d,γ,1 − ε) expander graph G with vertex set L∪̇R by brute force using Theorem 2.6, then we need to consider all possible subset S ⊆ R such that von(S) = ∅. But because of Theorem 2.7, we need to look at only S ⊆ R satisfying |S| > 2(1−ε)γn. Example 2.11. Consider the expander code C(G) of the (5,4,2, 1 2 , 2 3 ) expander graph G in Figure 1. Note that 1 − ε = 2 3 . By Theorem 2.7, we need to look at only S ⊆ R satisfying |S| > 2(1 − ε)γn = 8 3 . So we look at nonempty sets S ⊆ R satisfying |S| ≥ 3 and verify whether von(S) = ∅. For S = {6,8,9}, von(S) = ∅. Thus by Theorem 2.6, d(C(G)) = min{|S| : ∅ 6= S ⊆ R, von(S) = ∅} = |{6,8,9}| = 3. Acknowledgment: The author would like to thank his colleague Dr. Bahattin Yildiz for his valuable suggestions. The author would also like to thank the anonymous referee for the quick review. 83 S. Mallik / J. Algebra Comb. Discrete Appl. 9(2) (2022) 79–84 References [1] N. Alon, J. Bruck, J. Naor, M. Naor, R. Roth, Construction of asymptotically good low-rate error- correcting codes through pseudo-random graphs, IEEE Trans. Inf. Theory 38(2) (1992) 509–516. [2] M. R. Capalbo, O. Reingold, S. Vadhan, A. Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the ACM Symposium on Theory of Computing (2002) 659–668. [3] Sudipta Mallik, Bahattin Yildiz, Graph theoretic aspects of minimum distance and equivalence of binary linear codes, Australas. J. Combin. 79(3) (2021) 515–526. [4] Sudipta Mallik, Bahattin Yildiz, Isodual and self-dual codes from graphs, Algebra Discrete Math. 32(1) (2021) 49–64. [5] R. M. Roth, Introduction to coding theory, Cambridge University Press (2006). [6] M. Sipser, D. Spielman, Expander codes, IEEE Trans. Inf. Theory 42(6) (1996) 1710–1722. [7] M. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inf. Theory 27(5) (1981) 533–547. [8] G. Zemor, On expander codes, IEEE Trans. Inf. Theory 47(2) (2001) 835-837. 84 https://doi.org/10.1109/18.119713 https://doi.org/10.1109/18.119713 https://doi.org/10.1145/509907.510003 https://doi.org/10.1145/509907.510003 https://mathscinet.ams.org/mathscinet-getitem?mr=4224400 https://mathscinet.ams.org/mathscinet-getitem?mr=4224400 http://dx.doi.org/10.12958/adm1645 http://dx.doi.org/10.12958/adm1645 https://doi.org/10.1017/CBO9780511808968 https://doi.org/10.1109/18.556667 https://doi.org/10.1109/TIT.1981.1056404 https://doi.org/10.1109/TIT.1981.1056404 https://doi.org/10.1109/18.910593 Introduction Main results References