🔢 mathematics

Binary LCD Codes and Their Graph Representations

This paper provides a complete characterization of simple graphs and distance-regular graphs whose adjacency matrices generate binary linear complementary dual (LCD) codes, unifying previous results for specific graph families and applying these findings to distinguish inequivalent codes from conference graphs and classify small graphs with idempotent adjacency matrices.

Original authors: Keita Ishizuka

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Keita Ishizuka

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have two different worlds: one is Coding Theory (where people design secret messages and error-correcting codes) and the other is Graph Theory (where people study networks of dots and lines, like social networks or subway maps).

For a long time, mathematicians knew these two worlds were related, but they didn't have a perfect "dictionary" to translate between them. This paper, by Keita Ishizuka, builds that dictionary. It creates a perfect, one-to-one bridge between a specific type of secret code and a specific type of network.

Here is the breakdown of the paper's discoveries in simple terms:

1. The Two Worlds

The Code World (LCD Codes): Think of these as special "secret messages." A key feature of these messages is that they are "self-checking" in a very specific way. If you try to find a message that is hidden inside the code and its own "shadow" (mathematical opposite), you find nothing. This makes them very secure and useful for cryptography.
The Graph World: Think of these as simple maps of dots (vertices) connected by lines (edges). No loops (a dot connecting to itself) and no double lines between the same two dots.

2. The Big Discovery: The "Idempotent" Bridge

The author found a magical rule that connects these two worlds. He proved that every special "even" secret code corresponds to exactly one simple network, and vice versa.

But not just any network. The network must follow a strange rule called idempotence.

The Analogy: Imagine you have a network map. If you take a "step" from any dot to a neighbor, and then take another "step" from there, the result of doing this twice is mathematically the same as doing it once (in the world of binary math, where 1+1=0).
The Translation:
- If you have a code that works this way, you can draw a map of dots and lines that represents it perfectly.
- If you have a map where the dots and lines follow this "double-step" rule, you can write a secret code that represents it perfectly.
- Crucially: If two codes are just "shuffled" versions of each other, their maps are just "renamed" versions of each other (isomorphic). This means solving the puzzle of "are these two codes the same?" is exactly the same as solving "are these two maps the same?"

3. The Rules of the Game (What Makes a Map Work?)

The paper doesn't just say "some maps work." It gives a strict checklist for when a map (specifically a highly organized one called a Distance-Regular Graph) will produce a valid code.

Think of a Distance-Regular Graph as a perfectly symmetrical city where every neighborhood looks exactly the same. The paper says this city will generate a valid code if and only if three specific numbers about the city's layout are "even" or "odd" in a specific way:

The Degree: Every person in the city must have an even number of friends.
The Neighbors: If two people are friends, they must share an odd number of mutual friends.
The Strangers: If two people are not friends, they must share an even number of mutual friends.

If a city follows these three rules, it creates a perfect code. If it breaks even one, it fails.

4. Applying the Rules to Famous Cities

The author tested this rule on famous types of networks to see which ones pass the test:

Complete Graphs (Everyone knows everyone): These work, but only if the total number of people is odd. (e.g., 3, 5, 7 people work; 4, 6, 8 do not).
Cycle Graphs (A circle of people): Only a triangle (3 people) works. A square, pentagon, or larger circle fails the rules.
Hamming Graphs (Like a 3D cube): These work only if the size of the alphabet used to build them is odd.
Johnson Graphs: These work only if the total number of items is odd.

5. Solving a Mystery: The "Conference Graph" Puzzle

There was a famous observation by other researchers (Haemers et al.) regarding "Conference Graphs" (a special type of network). They noticed that:

If you had two different maps that looked different (non-isomorphic), the codes they produced were also different.
They suspected this was always true, but couldn't prove it.

This paper proves it. Because the author built a perfect bridge where "different maps = different codes," it is now mathematically guaranteed that if you have two different Conference Graphs (with a specific size property), they will produce two completely different secret codes. This explains why the previous researchers saw this pattern.

6. The "Mass Formula" Census

Finally, the author used a clever counting trick (called a "mass formula") originally designed for codes to count the maps.

Instead of trying to draw every possible map with up to 13 dots (which would take forever), he counted the codes first.
Because of his bridge, counting the codes automatically counted the maps.
The Result: He successfully classified 1,208 unique, valid maps with up to 13 dots. He found that many of these were famous shapes (like the Petersen graph's cousin) and confirmed that no "tree" shapes (branching structures like family trees) could ever work, because they have "leaves" with only one friend (violating the "even friends" rule).

Summary

This paper is a "Rosetta Stone" for mathematicians. It proves that a specific type of secure code and a specific type of network are two sides of the same coin. It gives a simple checklist to see if a network makes a good code, solves a long-standing mystery about why different networks make different codes, and uses code-counting tricks to catalog thousands of unique networks.

Technical Summary: Binary LCD Codes and Their Graph Representations

Problem Statement

The paper addresses the fundamental problem of characterizing which simple graphs (graphs without loops or multiple edges) generate binary Linear Complementary Dual (LCD) codes via their adjacency matrices. While previous research established connections between graph spectra and code dimensions, and provided sufficient conditions for specific graph families (such as Strongly Regular Graphs) to yield LCD codes, a complete characterization was lacking. Furthermore, the relationship between code equivalence and graph isomorphism for LCD codes, while known to be reducible to Graph Isomorphism (GI), lacked a constructive bijection that could facilitate the systematic classification of graphs based on coding-theoretic tools.

The core challenge is to determine necessary and sufficient conditions for a graph's adjacency matrix $A$ to be idempotent over $\mathbb{F}_2$ (i.e., $A^2 = A$ ), as this property is equivalent to the row span of $A$ forming an LCD code.

Methodology

The author employs a dual approach combining algebraic coding theory and algebraic graph theory:

Orthogonal Projectors and Idempotence: The paper utilizes the structural property that a binary code $C$ is LCD if and only if its orthogonal projector $\Pi_C$ is a symmetric matrix satisfying $\Pi_C^2 = \Pi_C$ . The author establishes that for binary even LCD codes, this projector corresponds exactly to the adjacency matrix of a simple graph.
Combinatorial Characterization: By analyzing the idempotence condition $A^2 = A$ over $\mathbb{F}_2$ , the paper derives combinatorial constraints on the graph structure, specifically relating vertex degrees and the number of common neighbors between adjacent and non-adjacent vertices.
Distance-Regular Graph (DRG) Analysis: The paper applies the three-term recurrence relation of distance matrices for DRGs. This allows the reduction of the idempotence condition to explicit parity constraints on the intersection array parameters $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$ .
Mass Formulas for Classification: To classify graphs with idempotent adjacency matrices, the paper leverages existing mass formulas for binary LCD codes (developed by Carlet et al.). By establishing a bijection between inequivalent codes and non-isomorphic graphs, the author avoids exhaustive graph enumeration, instead using the known classification of LCD codes to infer the classification of the corresponding graphs.

Key Contributions

1. Necessary and Sufficient Characterization of DRGs

The paper provides a complete characterization of distance-regular graphs that yield binary even LCD codes. For a DRG with intersection array $\{b_0, \dots, b_{d-1}; c_1, \dots, c_d\}$ , the adjacency matrix generates an LCD code if and only if:

$b_0 \equiv 0 \pmod 2$ (valency is even);
$a_1 \equiv 1 \pmod 2$ , where $a_1 = b_0 - b_1 - c_1$ ;
$c_2 \equiv 0 \pmod 2$ .

This result generalizes and strengthens previous sufficient conditions for Strongly Regular Graphs (SRGs) by Key and Rodrigues, extending the scope to all distance-regular graphs.

2. Equivalence-Preserving Bijection

The paper establishes a bijection between:

Binary even LCD codes of length $n$ ;
Simple graphs on $n$ vertices with idempotent adjacency matrices over $\mathbb{F}_2$ .

Crucially, this bijection preserves equivalence: two codes are permutation equivalent if and only if their corresponding graphs are isomorphic. This allows for the translation of problems between coding theory and graph theory.

3. Combinatorial Conditions

A simple graph yields a binary even LCD code if and only if:

Every vertex has an even degree;
Any two adjacent vertices have an odd number of common neighbors;
Any two non-adjacent vertices have an even number of common neighbors.

4. Classification of Small Graphs

Using the bijection and mass formulas, the paper classifies all simple graphs with idempotent adjacency matrices on at most 13 vertices. From 22,213 binary LCD codes of length $n \le 13$ , the author identifies 1,208 non-isomorphic graphs, including known families such as complete graphs, complete multipartite graphs, and specific strongly regular graphs.

Results

Characterization of Specific Graph Families

The general DRG theorem yields sharp criteria for several well-known graph families:

Complete Graphs ( $K_n$ ): Yield an LCD code if and only if $n$ is odd.
Cycle Graphs ( $C_n$ ): Only $C_3$ (which is $K_3$ ) yields an LCD code; cycles with $n \ge 4$ do not.
Hamming Graphs ( $H(n, m)$ ): Yield an LCD code if and only if $m$ is odd.
Johnson Graphs ( $J(n, k)$ ): Yield an LCD code if and only if $n$ is odd.
Grassmann Graphs ( $J_q(n, k)$ ): Yield an LCD code if and only if $n$ is odd and $q$ is odd. If $q$ is even, they never yield an LCD code.

Conference Graphs and Haemers' Observation

The paper addresses a computational observation by Haemers, Peeters, and van Rijckevorsel regarding conference graphs (SRGs with parameters $(q, (q-1)/2, (q-5)/4, (q-1)/4)$ ).

Theoretical Proof: The paper proves that a conference graph yields a binary even LCD code if and only if $q \equiv 1 \pmod 8$ .
Equivalence: It confirms that non-isomorphic conference graphs with $q \equiv 1 \pmod 8$ yield inequivalent codes. This provides a theoretical explanation for the observation that non-isomorphic graphs in this class produce distinct codes, a property previously verified only computationally for specific cases like $srg(25, 12, 5, 6)$.

Computational Classification

For $n \le 13$ , the classification reveals:

44 graphs belonging to well-known families (6 complete graphs, 36 complete multipartite graphs, 2 strongly regular graphs).
The two strongly regular graphs identified are the Paley graph of order 9 ($srg(9, 4, 1, 2)$) and the complement of the Petersen graph ($srg(10, 6, 3, 4)$).
The codes generated by these specific graphs are confirmed to be optimal according to Grassl's tables.

Significance and Claims

The paper claims to bridge the gap between LCD code theory and graph theory by establishing a structural correspondence that is both necessary and sufficient.

Unification: The characterization unifies the treatment of complete, Hamming, Johnson, and Grassmann graphs under a single framework of distance-regularity.
Theoretical Explanation: It provides the first theoretical justification for the observation that non-isomorphic conference graphs yield inequivalent codes, moving beyond empirical verification.
Methodological Innovation: The work demonstrates that mass formulas, traditionally used for classifying codes, can be effectively repurposed to classify graphs with specific algebraic properties (idempotent adjacency matrices), offering a new tool for graph enumeration.
Open Problems: The paper modestly notes that while the Paley graph achieves the largest minimum distance for $srg(41, 20, 9, 10)$, it remains an open question whether the Paley graph is the unique optimizer for all conference graphs with $q \equiv 1 \pmod 8$ and $q > 41$ .