Drazin Inverses and Walk Structure of Oriented Dutch Windmill Graphs

1. Problem Statement

The paper addresses the challenge of determining the Drazin inverse and the Drazin index for the adjacency matrices of a specific class of directed graphs known as oriented Dutch windmill graphs ($D^m_n$).

• Context: While explicit Drazin inverses are known for simpler structures like paths, cycles, and bipartite graphs, deriving closed-form expressions for more complex digraphs with recursive cyclic structures remains difficult.
• Specific Object: The oriented Dutch windmill graph $D^m_n$ is constructed by coalescing $m$ copies of a directed cycle $C_n$ (where $n \geq 3$) at a single common vertex.
• Goal: To provide a constructive, combinatorial characterization of the Drazin inverse, determine the Drazin index, and establish the relationship between the graph's walk structure and the algebraic properties of its adjacency matrix.

2. Methodology

The authors employ a hybrid approach combining combinatorial enumeration of walks with algebraic matrix analysis.

• Walk Enumeration: The core of the method relies on analyzing the number and existence of walks of specific lengths ($n-1$, $2n-1$, $pn-1$, etc.) between vertices in $D^m_n$.
  • The authors rigorously classify walks based on whether they stay within a single cycle, traverse the central hub, or switch between cycles.
  • They prove that walks of length $n-1$ are unique (if they exist) and that walks of length $pn-1$ scale multiplicatively with the number of available cycles ($m$).
• Matrix Powers and Polynomials:
  • The $(i, j)$-entry of the adjacency matrix power $M^k$ corresponds to the number of walks of length $k$ from vertex $i$ to $j$.
  • By establishing relationships between walk counts at different lengths (e.g., relating walks of length $2n-1$ to those of length $n-1$), the authors derive polynomial identities satisfied by the adjacency matrix $M$.
• Algebraic Derivation:
  • Using the identified annihilating polynomial, they determine the Drazin index (the smallest $k$ such that $\text{rank}(M^k) = \text{rank}(M^{k+1})$).
  • They utilize the core-nilpotent decomposition and properties of the minimal polynomial to construct the explicit formula for the Drazin inverse ($M^D$).

3. Key Contributions and Results

A. Combinatorial Walk Structure

The paper establishes precise lemmas regarding walk existence and uniqueness:

• Length $n-1$: Walks of this length exist only between specific vertex pairs (e.g., from the hub to the end of a cycle, or between specific nodes in different cycles). Crucially, if such a walk exists, it is unique.
• Length $pn-1$($p \geq 2$): The number of walks of length $pn-1$ between two vertices is exactly $m^{p-1}$ times the number of walks of length $n-1$. This reveals a multiplicative scaling factor driven by the $m$ available cycles.

B. Algebraic Properties of the Adjacency Matrix ($M$)

The authors prove the following properties for the adjacency matrix $M$ of $D^m_n$ (where $m \geq 2$):

1. Annihilating Polynomial: The matrix satisfies the equation:
   $$M^{2n-1} = m M^{n-1}$$
   This implies the polynomial $\phi(\lambda) = \lambda^{n-1}(\lambda^n - m)$ annihilates $M$.
2. Drazin Index: The Drazin index of $M$ is $n-1$.
   • This is derived because $\lambda^{n-1}$ is the highest power of $\lambda$ dividing the minimal polynomial, and $M^{n-1} \neq 0$.
   • Consequently, for $n \geq 3$, the index is $\geq 2$, meaning $M$ does not possess a group inverse (which requires an index $\leq 1$).
3. Non-Invertibility: For $m > 1$, the matrix $M$ is singular.

C. Explicit Formula for the Drazin Inverse

The paper derives a closed-form expression for the Drazin inverse:
$$M^D = \frac{1}{m} M^{n-1}$$

• Structure of $M^D$: The Drazin inverse is simply a scaled version of the $(n-1)$-th power of the adjacency matrix.
• Non-zero Entries: The non-zero entries of $M^D$ are all equal to $1/m$.
• Support: A non-zero entry exists at position $(i, j)$ if and only if there is a unique walk of length $n-1$ from $i$ to $j$. The paper explicitly lists these vertex pairs, which include:
  • The central vertex to the "end" of any cycle.
  • The "start" of any cycle (after the hub) back to the central vertex.
  • Specific transitions within a single cycle or between different cycles that align with the $n-1$ length constraint.

4. Significance and Implications

• Theoretical Bridge: The work provides a concrete example of how the combinatorial topology of a graph (specifically the arrangement of cycles and walk lengths) directly dictates the algebraic structure of its generalized inverses.
• Generalization: It extends known results for paths and cycles to a more complex, recursively structured family of graphs, offering a template for analyzing other coalescent digraphs.
• Computational Utility: The explicit formula $M^D = \frac{1}{m} M^{n-1}$ allows for the symbolic computation of the Drazin inverse without needing complex numerical algorithms, which is valuable for discrete dynamical systems and Markov chains defined on such networks.
• Insight into Singular Systems: The results offer deeper understanding of singular systems governed by cyclic feedback, showing how the "depth" of the cyclic structure (parameter $n$) determines the algebraic complexity (index) of the system's pseudo-inverse.

In summary, the paper successfully solves the problem of finding the Drazin inverse for oriented Dutch windmill graphs by proving that the inverse is a scaled power of the adjacency matrix, where the scaling factor and the power are determined entirely by the graph's cycle count ($m$) and cycle length ($n$).