Eigen-values/vectors

A quick math review

Linear Algebra

  • Linear algebra is a branch of mathematics that deals with linear equations and their representation through matrices and vectors, used in various fields in science

Transformations

Transformation Matrices: Columns as Transformed Basis Vectors

Key insight the columns of \(A\) are exactly where the standard basis vectors \(\mathbf{e}_1, \mathbf{e}_2\) land after transformation.

\[A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}, \quad \mathbf{e}_1 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \quad \mathbf{e}_2 = \begin{pmatrix} 0 \\ 1 \end{pmatrix}\]

\[A\mathbf{e}_1 = \begin{pmatrix} a & b \\ c & d \end{pmatrix}\begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} a \\ c \end{pmatrix} \leftarrow \text{column 1}\]

\[A\mathbf{e}_2 = \begin{pmatrix} a & b \\ c & d \end{pmatrix}\begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} b \\ d \end{pmatrix} \leftarrow \text{column 2}\]

Example: a 90° counter-clockwise rotation

\[A = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \quad \rightarrow \quad \mathbf{e}_1 = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \mapsto \begin{pmatrix} 0 \\ 1 \end{pmatrix}, \quad \mathbf{e}_2 = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \mapsto \begin{pmatrix} -1 \\ 0 \end{pmatrix}\]

Why this matters: Any vector \(\mathbf{x} = x_1\mathbf{e}_1 + x_2\mathbf{e}_2\) transforms linearly, so its image under \(A\) is

\[ \tilde{\mathbf{x}} = A\mathbf{x} = x_1 A\mathbf{e}_1 + x_2 A\mathbf{e}_2=x_1\tilde{\mathbf{e}}_1+x_2\tilde{\mathbf{e}}_2, \]

where \(\tilde{\mathbf{x}}\) denotes the transformed vector. Because \(A\mathbf{e}_1\) and \(A\mathbf{e}_2\) are just the images of the basis vectors (the columns of \(A\)), knowing where each basis vector goes (i.e., \(\mathbf{e}_1 \mapsto \tilde{\mathbf{e}}_1 = A\mathbf{e}_1\), \(\mathbf{e}_2 \mapsto \tilde{\mathbf{e}}_2 = A\mathbf{e}_2\)) tells you everything about how \(A\) transforms all vectors.

Matrix Inversion

A square matrix \(A\) is invertible if there exists a matrix \(A^{-1}\) such that:

\[ A A^{-1}=A^{-1} A=I \]

(where \(I\) is the identity matrix). A matrix has an inverse if and only if its determinant is non-zero ( \(\operatorname{det}(A) \neq 0\) ).

Common Methods for Computing Inverses

  1. Analytic Methods (Exact / Formula-based): Best for small matrices ( \(2 \times 2\) or \(3 \times 3\) ) and theoretical proofs.
    • Adjugate Matrix Method (Cramer’s Rule): \(A^{-1}=\frac{1}{\operatorname{det}(A)} \operatorname{adj}(A)\). Computes the matrix of cofactors, transposes it, and divides by the determinant. Becomes computationally impossible for large matrices due to \(O(n!)\) or \(O\left(n^3\right)\) determinant calculations.
    • The Adjugate matrix is the transpose of the matrix of cofactors, where the cofactors are the determinants of the submatrices obtained by deleting the row and column of the element, multiplied by \((-1)^{i+j}\).
  2. Numeric Methods (Algorithmic / Computer-based): Used by software for large, real-world matrices.
    • Gauss-Jordan Elimination: Convert the augmented matrix \([A \mid I]\) into \(\left[I \mid A^{-1}\right]\) using elementary row operations.
    • LU Decomposition: Decomposes \(A\) into lower \((L)\) and upper \((U)\) triangular matrices ( \(A= L U)\), then solves \(L U X=I\) using forward and backward substitution. This is the industry standard for computational efficiency ( \(O\left(n^3\right)\) complexity).

Numerical example: 2x2

  • np.linalg.inv(A) does numerical inversion using the LU decomposition method
  • Under the hood, np.linalg.inv(A) relies on highly optimized C and Fortran libraries called BLAS and LAPACK.
    • Specifically, it typically wraps LAPACK routines like _GESV (or _GETRF combined with _GETRI), which perform numerical matrix inversion using LU decomposition with
Code
## simple matrix inversion
import numpy as np

A = np.array([[4, 7], [2, 6]])

print(np.linalg.inv(A))
[[ 0.6 -0.7]
 [-0.2  0.4]]

Analytic example: 2x2

Simple \(2 \times 2\) Example To find the inverse of a \(2 \times 2\) matrix, swap the positions of \(a\) and \(d\), put negative signs in front of \(b\) and \(c\), and divide everything by the determinant \((a d-b c)\).

Matrix \(A\) :

\[ A=\left(\begin{array}{ll} 4 & 7 \\ 2 & 6 \end{array}\right) \]

1 Find Determinant: \(\operatorname{det}(A)=(4 \times 6)-(7 \times 2)=24-14=10\) 2 Apply \(2 \times 2\) Formula:

\[ A^{-1}=\frac{1}{10}\left(\begin{array}{cc} 6 & -7 \\ -2 & 4 \end{array}\right)=\left(\begin{array}{cc} 0.6 & -0.7 \\ -0.2 & 0.4 \end{array}\right) \]

Numerical example: 3x3

Code
x=np.array([[1, 0, 2], [2, -1, 3], [4, 1, 8]])
print(np.linalg.inv(x))
[[-11.   2.   2.]
 [ -4.  -0.   1.]
 [  6.  -1.  -1.]]

Analytic example: 3x3

Find the inverse (\(A^{-1}\)) of the following matrix \(A\):

\[A = \begin{pmatrix} 1 & 0 & 2 \\ 2 & -1 & 3 \\ 4 & 1 & 8 \end{pmatrix}\]

Step 1: Calculate the Determinant (\(\det(A)\))

We will expand along the first row because it contains a zero, which makes the math easier.

\[\det(A) = 1 \cdot \begin{vmatrix} -1 & 3 \\ 1 & 8 \end{vmatrix} - 0 \cdot \begin{vmatrix} 2 & 3 \\ 4 & 8 \end{vmatrix} + 2 \cdot \begin{vmatrix} 2 & -1 \\ 4 & 1 \end{vmatrix}\]

  • \(\begin{vmatrix} -1 & 3 \\ 1 & 8 \end{vmatrix} = (-1 \times 8) - (3 \times 1) = -8 - 3 = -11\)
  • \(\begin{vmatrix} 2 & -1 \\ 4 & 1 \end{vmatrix} = (2 \times 1) - (-1 \times 4) = 2 + 4 = 6\)

\[\det(A) = 1(-11) - 0 + 2(6) = -11 + 12 = 1\]

Since \(\det(A) = 1\) (which is non-zero), the matrix is invertible.

Step 2: Find the Matrix of Minors

For each element, temporarily cross out its row and column, and calculate the determinant of the remaining 2x2 matrix.

  • Top Row:

  • \(M_{11} = \begin{vmatrix} -1 & 3 \\ 1 & 8 \end{vmatrix} = -11\)

  • \(M_{12} = \begin{vmatrix} 2 & 3 \\ 4 & 8 \end{vmatrix} = (16 - 12) = 4\)

  • \(M_{13} = \begin{vmatrix} 2 & -1 \\ 4 & 1 \end{vmatrix} = (2 - (-4)) = 6\)

  • Middle Row:

  • \(M_{21} = \begin{vmatrix} 0 & 2 \\ 1 & 8 \end{vmatrix} = (0 - 2) = -2\)

  • \(M_{22} = \begin{vmatrix} 1 & 2 \\ 4 & 8 \end{vmatrix} = (8 - 8) = 0\)

  • \(M_{23} = \begin{vmatrix} 1 & 0 \\ 4 & 1 \end{vmatrix} = (1 - 0) = 1\)

  • Bottom Row:

  • \(M_{31} = \begin{vmatrix} 0 & 2 \\ -1 & 3 \end{vmatrix} = (0 - (-2)) = 2\)

  • \(M_{32} = \begin{vmatrix} 1 & 2 \\ 2 & 3 \end{vmatrix} = (3 - 4) = -1\)

  • \(M_{33} = \begin{vmatrix} 1 & 0 \\ 2 & -1 \end{vmatrix} = (-1 - 0) = -1\)

Putting them together gives the Matrix of Minors:

\[\text{Minors} = \begin{pmatrix} -11 & 4 & 6 \\ -2 & 0 & 1 \\ 2 & -1 & -1 \end{pmatrix}\]

Step 3: Apply the Checkerboard of Signs (Matrix of Cofactors)

Apply a grid of alternating signs \(\begin{pmatrix} + & - & + \\ - & + & - \\ + & - & + \end{pmatrix}\) to the matrix of minors. This changes the sign of elements at \(M_{12}\), \(M_{21}\), \(M_{23}\), and \(M_{32}\):

\[\text{Cofactors}(C) = \begin{pmatrix} -11 & -4 & 6 \\ 2 & 0 & -1 \\ 2 & 1 & -1 \end{pmatrix}\]

Step 4: Transpose the Cofactor Matrix (Adjugate Matrix)

Flip the rows and columns of the cofactor matrix (row 1 becomes column 1, etc.).

\[\text{adj}(A) = C^T = \begin{pmatrix} -11 & 2 & 2 \\ -4 & 0 & 1 \\ 6 & -1 & -1 \end{pmatrix}\]

Step 5: Divide by the Determinant

The formula is \(A^{-1} = \frac{1}{\det(A)} \cdot \text{adj}(A)\). Since our determinant is \(1\), the adjugate matrix is our final answer!

\[A^{-1} = \frac{1}{1} \begin{pmatrix} -11 & 2 & 2 \\ -4 & 0 & 1 \\ 6 & -1 & -1 \end{pmatrix} = \begin{pmatrix} -11 & 2 & 2 \\ -4 & 0 & 1 \\ 6 & -1 & -1 \end{pmatrix}\]

(To double-check this, multiplying \(A \times A^{-1}\) will result in the 3x3 Identity Matrix).

Invertible vs. Non-Invertible Matrices, Geometrically

Invertible: \(A\) is a one-to-one, reversible transformation of space

  • Maps \(\mathbb{R}^n\) to all of \(\mathbb{R}^n\), every point is reachable
  • Preserves dimensionality: a plane stays a plane, a line stays a line
  • \(|\det(A)| > 0\), volume is scaled but never destroyed
  • The transformation can be undone: \(A^{-1}\) exists

Non-Invertible (Singular): \(A\) collapses space into a lower-dimensional subspace

  • Maps \(\mathbb{R}^n\) into a strict subspace, some points become unreachable
  • Destroys dimensionality: a 3D space may collapse to a plane, line, or point
  • \(\det(A) = 0\), volume is annihilated
  • The transformation cannot be undone: information is permanently lost

Simple example:

\[A = \begin{pmatrix} 2 & 0 \\ 0 & 3 \end{pmatrix} \xrightarrow{\text{invertible}} \text{stretches plane, } \det = 6\]

\[B = \begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix} \xrightarrow{\text{singular}} \text{collapses plane to a line, } \det = 0\]

Key intuition: invertibility is about whether \(A\) preserves the “richness” of space, singular matrices are the ones that irreversibly flatten it.

Transformed area

The two columns of \(A\) are the transformed basis vectors \(\tilde{\mathbf{e}}_1= (a_{11}, a_{21})^{\top}\) and \(\tilde{\mathbf{e}}_2=(a_{12}, a_{22})^{\top}\), which form a parallelogram.

The Determinant & Its Geometric Meaning

Algebraically a scalar \(\det(A)\) computed from an \(n \times n\) matrix that encodes whether \(A\) is invertible

Geometrically \(|\det(A)|\) is the factor by which \(A\) scales volume

\[\det\begin{pmatrix} a & b \\ c & d \end{pmatrix} = ad - bc\]

\(\det(A)\) Meaning
\(= 0\) \(A\) collapses space: not invertible
\(> 0\) Volume scaled by \(\det(A)\), orientation preserved
\(< 0\) Volume scaled by \(|\det(A)|\), orientation flipped
\(= 1\) Volume unchanged (e.g., rotation)

2D example columns \(\mathbf{a}_1, \mathbf{a}_2\) form a parallelogram: \(|\det(A)|\) is its area

\[A = \begin{pmatrix} 3 & 0 \\ 0 & 2 \end{pmatrix} \rightarrow \det(A) = 6 \quad \text{(unit square} \mapsto \text{rectangle of area 6)}\]

\[B = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix} \rightarrow \det(B) = (2)(2) - (1)(1) = 4 - 1 = 3 \quad \text{(unit square} \mapsto \text{parallelogram of area 3)}\]

Key properties

  • \(\det(AB) = \det(A)\det(B)\): volume scaling compounds multiplicatively
  • \(\det(A^{-1}) = 1/\det(A)\): the inverse undoes the scaling
  • \(\det(A^\top) = \det(A)\): transposing doesn’t change volume scaling

The Invertible Matrix Theorem

  • A square matrix \(A\) is invertible (i.e., has an inverse \(A^{-1}\)) if and only if the following equivalent statements hold
  1. \(A\) is invertible (nonsingular)
  2. \(\det(A) \neq 0\)
  3. The equation \(A\mathbf{x} = \mathbf{0}\) has only the trivial solution (\(\mathbf{x} = \mathbf{0}\))
  4. The columns of \(A\) are linearly independent
  5. The columns of \(A\) span \(\mathbb{R}^n\)
  6. The rank of \(A\) is \(n\)
  7. \(A\) can be row reduced to the identity matrix
  8. \(A\) has \(n\) pivot positions
  9. The linear transformation \(\mathbf{x} \mapsto A\mathbf{x}\) is one-to-one and onto
  10. The eigenvalue \(0\) is not an eigenvalue of \(A\)

All these conditions are equivalent for an \(n \times n\) matrix \(A\)! (If any one is true, all are true; if any one is false, all are false.)

Intuition behind the Invertible Matrix Theorem

All these conditions say the same thing \(A\) loses no information.

  • \(\det(A) \neq 0\): the matrix doesn’t collapse volume to zero; it stretches/rotates space without flattening it
  • \(A\mathbf{x} = \mathbf{0}\) has only \(\mathbf{x} = \mathbf{0}\): nothing gets “erased”; the only input that maps to zero is zero itself
  • Columns are linearly independent: no column is redundant; each one points in a genuinely new direction
  • Columns span \(\mathbb{R}^n\): the matrix can reach every point in space, so no output is “unreachable”
  • Rank \(= n\): all \(n\) dimensions are used; none are lost in the transformation
  • Row reduces to \(I\): \(A\) can be fully “undone” by elementary operations, confirming an inverse exists
  • \(n\) pivot positions: every row and column does independent work; no redundancy, no collapse
  • \(T\) is one-to-one and onto: distinct inputs give distinct outputs (one-to-one), and every output is reachable (onto); together, \(T\) is perfectly reversible
  • \(\lambda = 0\) is not an eigenvalue: if \(0\) were an eigenvalue, some nonzero vector would map to \(\mathbf{0}\), meaning \(A\) collapses space: exactly what invertibility forbids

Eigen vectors/values

Eigen vectors/values

Visualization

  • A 2×2 real and symmetric matrix representing a stretching and shearing of the plane. The eigenvectors of the matrix (red lines) are the two special directions such that every point on them will just slide on them.

Solving an Eigenvalue Problem

  • Set up \((A - \lambda I)\mathbf{x} = \mathbf{0}\): what scalars \(\lambda\) make \(A\) act like pure stretching?

  • Find eigenvalues via \(\det(A - \lambda I) = 0\): a nonzero solution exists only if \(A - \lambda I\) is singular

    • This is the Invertible Matrix Theorem flipped:
    • Finding eigenvalues is finding the \(\lambda\) values for which \(A - \lambda I\) fails the IMT: opening the door to nontrivial eigenvectors.

\[A \text{ invertible} \iff \det(A) \neq 0 \iff A\mathbf{x} = \mathbf{0} \text{ has only } \mathbf{x} = \mathbf{0}\]

\[\det(A - \lambda I) = 0 \iff (A - \lambda I) \text{ singular} \iff (A-\lambda I)\mathbf{x} = \mathbf{0} \text{ has a nonzero solution}\]

  • Find eigenvectors by substituting each \(\lambda\) back: the null space of \(A - \lambda I\) reveals which directions are purely stretched

  • Interpret each \((\lambda, \mathbf{x})\) pair: \(\mathbf{x}\) is a direction \(A\) leaves invariant, scaled by \(\lambda\)

Left and Right Eigenvalue Problems

A right eigenvector is a direction that \(A\) merely stretches when acting on column vectors from the left \((A \mathbf{x}=\lambda \mathbf{x})\), while a left eigenvector is a row vector that gets stretched when it acts on \(A\) from the left ( \(\mathbf{y}^{\top} A=\lambda \mathbf{y}^{\top}\) ), same eigenvalues, just the matrix acting from opposite sides.

Running example \(A = \begin{pmatrix} 2 & 1 \\ 0 & 3 \end{pmatrix}\), with eigenvalues \(\lambda = 2, 3\)

Right eigenvectors (the usual case)

\[A\mathbf{x} = \lambda \mathbf{x} \quad\rightarrow\quad \begin{pmatrix} 2 & 1 \\ 0 & 3 \end{pmatrix}\begin{pmatrix} 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 3 \\ 3 \end{pmatrix} = 3\begin{pmatrix} 1 \\ 1 \end{pmatrix}\]

  • Column vector \(\mathbf{x}\), multiplied on the right of \(A\)

Left eigenvectors

\[\mathbf{y}^\top A = \lambda \mathbf{y}^\top \quad\rightarrow\quad \begin{pmatrix} 0 & 1 \end{pmatrix}\begin{pmatrix} 2 & 1 \\ 0 & 3 \end{pmatrix} = \begin{pmatrix} 0 & 3 \end{pmatrix} = 3\begin{pmatrix} 0 & 1 \end{pmatrix}\]

  • Row vector \(\mathbf{y}^\top\), multiplied on the left of \(A\)
  • Equivalent to a right eigenvector of \(A^\top\)

Key facts

  • Same eigenvalues \(\lambda\) in both problems
  • If \(A\) is symmetric, left and right eigenvectors coincide

Analytic example: Eigenvalue Problem

  • The characteristic polynomial \(\det(A - \lambda I)\) is always degree \(n\) for an \(n \times n\) matrix, giving exactly \(n\) eigenvalues (counting multiplicity, over \(\mathbb{C}\)). One stretching direction per dimension of the space.

  • Notice that there are \(n\) eigenvalues and \(n\) eigenvectors, one per dimension of the space.

Looking ahead: Adjacency matrix

IMPORTANT: Whenever you encounter a well-defined, mathematically meaningful square matrix—especially one with a clear real-world interpretation—it makes sense to analyze its eigenvectors. Examples include the adjacency matrix, covariance matrix, and others.

  • Element \(a_{i j}\) of the adjacency matrix represents the link between nodes \(i\) and \(j . a_{i j}=1\) if \(i\) and \(j\) are adjacent, \(a_{i j}=0\) otherwise.
  • When you encounter a square matrix, particularly if it has a well defined real-world interpretation, it is logical to analyze the Eigen-vectors.

Famous square matrices:

  • The Adjacency Matrix (Network Science & ML): Defines connections between nodes in a graph; its principal eigenvector yields eigencentrality scores, which rank nodes based on their overall influence and connectivity within the network.
  • The Covariance Matrix (Machine Learning): Yields the principal components (eigenvectors), which identify the directions of maximum variance in a dataset for dimensionality reduction (PCA).
  • The Inertia Tensor (Physics): Identifies the principal axes of inertia (eigenvectors), showing the specific axes about which an object can rotate cleanly without wobbling.
  • The Graph Laplacian (Machine Learning & Network Science): Reveals structural network partitions; the eigenvector corresponding to the second-smallest eigenvalue provides the mathematically optimal way to split a graph into communities (Spectral Clustering).
  • The Hessian Matrix (Machine Learning): Determines the local curvature of a loss function landscape, where the signs and magnitudes of the eigenvalues identify whether a point is a minimum, maximum, or saddle point.
  • The Hamiltonian Matrix (Physics): Solves the Schrödinger equation, where the eigenvalues provide the exact allowed energy levels of a quantum system and the eigenvectors represent its stable quantum states.
  • The Density Matrix (Quantum Mechanics & Quantum ML): Allows for the extraction of pure states from a statistical mixture and is used to compute Von Neumann entropy to measure quantum entanglement.
  • The Stress Tensor (Physics): Uncovers the principal stress directions (eigenvectors), indicating the precise planes of maximum tension or compression where a material is most likely to fracture.

Eigen-centrality

The Spectral Theorem: Why Symmetry Is a Gift in Network Analysis

  • The spectral theorem says any real symmetric matrix has all real eigenvalues and a full set of orthogonal eigenvectors, so it can be written as \(A = Q\Lambda Q^{T}\): a clean rotation into a coordinate system where the matrix is just a diagonal stretch.
  • Why networks care: undirected graphs have symmetric adjacency and Laplacian matrices, so the theorem applies and the eigenvectors become a natural basis for any signal living on the nodes.
  • It is the bedrock under a huge amount of method. Eigenvector centrality is well-posed (a unique, real, positive leading eigenvector), spectral clustering and graph partitioning split the graph along the low-eigenvalue eigenvectors, and diffusion, heat kernels, and random walks all decompose cleanly into independent eigen-modes.
  • The intuition: orthogonal eigenvectors are non-interfering directions. A process on the graph can be broken into independent modes that each just decay or grow at their own rate, which is what makes the analysis tractable.
  • The catch, and the thread through this unit: direction breaks symmetry. An asymmetric adjacency matrix can have complex eigenvalues, may not diagonalize, and splits left from right eigenvectors. Losing the spectral theorem is precisely why directed eigenvector centrality misbehaves and why fixes like Katz and PageRank exist.

Overview

  • Eigen-centrality is a prestige score which measures the node’s influence
  • It is a nodal attribute, as is the case with all other centrality measures.
  • Connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes
  • A high Eigen-centrality means the node is connected to many nodes with high scores.
  • Google’s PageRank and the Katz centrality are variants of the eigenvector centrality.

Big picture

  • Degree centrality asks how many connections does a node have?
  • Eigenvector centrality asks a deeper question how important are the nodes you are connected to?
  • Core intuition a node is important if it is connected to other important nodes
  • The definition is recursive, your score depends on your neighbors’ scores, which depend on their neighbors’ scores, and so on
  • Classic analogy being friends with 10 well-connected people may matter more than being friends with 50 isolated people

Why It Matters

  • Captures influence, not just popularity
    • Social networks a person followed by celebrities vs. a person followed by bots
    • Citation networks being cited by landmark papers vs. obscure ones
  • Foundation for famous algorithms
    • PageRank (Google) and Katz centrality are direct descendants
  • Used in epidemiology (super-spreaders), economics (systemic risk), neuroscience (hub regions)

Dimensionality of the Eigencentrality Vector

For a network with \(n\) nodes, the adjacency matrix \(A\) is \(n \times n\), and the eigenvector equation is:

\[A\mathbf{x} = \lambda \mathbf{x}, \quad \mathbf{x} \in \mathbb{R}^n\]

  • \(\mathbf{x}\) has one entry per node, the eigencentrality of node \(i\) is simply the scalar \(x_i\)
  • The full vector \(\mathbf{x} = (x_1, x_2, \ldots, x_n)^\top\) is the centrality profile of the entire network
  • The degree of the characteristic polynomial is \(n\), so there are \(n\) eigenvector solutions, one per dimension of the network

Intuition: the eigenvector lives in “node space”, each axis corresponds to a node, and the eigenvector assigns a score along each axis simultaneously, subject to the self-consistency condition across the whole network.

Setting Intuition for Eigenvector Centrality

Core idea: a node is important if it is connected to other important nodes, importance is self-referential.

Setup: let \(x_i\) be the centrality of node \(i\). We want each node’s score to be proportional to the sum of its neighbors’ scores:

\[x_i \propto \sum_{j \in \mathcal{N}(i)} x_j \quad \rightarrow \quad \mathbf{x} \propto A\mathbf{x} \quad \rightarrow \quad A\mathbf{x} = \lambda \mathbf{x}\]

This is a self-consistency condition: we seek a centrality assignment where every node’s score is simultaneously explained by its neighbors’ scores, which are explained by their neighbors, and so on.

  • We don’t assume neighbors have similar scores
  • We look for a global fixed point: an assignment that wouldn’t change if you recomputed every node from its neighbors at once
  • The eigenvalue \(\lambda\) is simply the scaling factor that makes this balance globally

This is exactly what the eigenvector equation captures: the one centrality vector stable under the entire network’s structure.

Definition

Let \(A\) be the adjacency matrix of an undirected graph, where \(A_{ij} = 1\) if nodes \(i\) and \(j\) are connected.

The centrality \(x_i\) of node \(i\) is proportional to the sum of its neighbors' centralities

\[ x_i = \frac{1}{\lambda} \sum_{j} A_{ij}, x_j \]

In matrix form, this is an eigenvalue problem

\[ A\mathbf{x} = \lambda \mathbf{x} \]

The Perron–Frobenius Theorem in Eigencentrality

  • By the Perron–Frobenius theorem, choosing \(\lambda = \lambda_{\max}\) (the largest eigenvalue) guarantees an eigenvector with all non-negative entries, the only choice that makes sense as a centrality score
  • Scores are typically normalized so that \(\lVert \mathbf{x} \rVert_2 = 1\)
  • Eigencentrality ranks nodes recursively: “You are important if other important nodes link to you.” This maps to the eigenvector equation \(Av = \lambda v\), where \(A\) is the adjacency matrix.

The Perron–Frobenius Theorem is the mathematical guarantee that this recursive definition yields a valid, stable ranking.

The 3 Core Guarantees

For any strongly connected network (where every node can reach every other node), the theorem guarantees that the matrix \(A\):

  1. Has a Unique Maximum: Possesses a single, unique largest real eigenvalue (\(\lambda_{\max}\)).
  2. Yields Positive Scores: The corresponding principal eigenvector \(v\) has strictly positive components (\(v_i > 0\)). Every node receives a meaningful, non-zero score.
  3. Is Unambiguous: No other positive eigenvectors exist, ensuring a definitive ranking.

The Directed Graph Problem (Sinks & Dead Ends)

  • Undirected Graphs: If connected, they naturally meet the theorem’s criteria.
  • Directed Graphs: Often break the theorem because they contain sinks (nodes with incoming edges but no outgoing edges).

Without outgoing edges to recirculate influence, the matrix loses its mathematical “irreducibility.” Consequently, the Perron–Frobenius guarantees collapse, and the centrality scores of entire clusters can drain away, dropping to zero. This fatal flaw is why PageRank introduces a “damping factor” (random teleportation)—it artificially restores strong connectivity so the Perron–Frobenius theorem can function properly.

NetworkX

  • The following command computes the eigenvector centrality for the graph \(\mathrm{G}\).

eigenvector_centrality(G, max_iter=100, tol=1e-06, nstart=None, weight=None)

  • Eigenvector centrality computes the centrality for a node based on the centrality of its neighbors.
  • The eigenvector centrality for node \(i\) is the \(i\)-th element of the vector \(x\) defined by the equation \[ A x=\lambda x \]
  • where \(A\) is the adjacency matrix of the graph \(\mathrm{G}\) with eigenvalue \(\lambda\).
  • By virtue of the Perron-Frobenius theorem, there is a unique solution \(x\), all of whose entries are positive, if \(\lambda\) is the largest eigenvalue of the adjacency matrix \(A\).

Example

Code
import networkx as nx
import numpy as np

# CREATE-1
G=nx.complete_graph(3)

# CREATE-2
# G = nx.DiGraph()
# G = nx.Graph()
# G.add_nodes_from([0,1,2,3,4])
# G.add_edges_from([(0, 1), (0, 2), (0,3), (0,4),(1,0),(2,3)])

# DRAW
nx.draw(G)

# ADJACENCY MATRIX
A=nx.adjacency_matrix(G).todense()
print("Adjacency matrix\n",A)

# METHOD-1: NETWORKX EIGENVECTOR_CENTRALITY
print("\nEIGENVECTOR_CENTRALITY:\n",nx.eigenvector_centrality(G))

# METHOD-2: COMPUTE FROM "SCRATCH"
print("EIGENVALUES:",np.linalg.eig(A)[0])
eVect=np.array(np.linalg.eig(A)[1])
print("\nEIGENVECTORS:\n",np.round(eVect,4))
print("LENGTH OF EIGEN VECTORS:",
np.sqrt(np.sum((eVect)**2,axis=0))**0.5)
Adjacency matrix
 [[0 1 1]
 [1 0 1]
 [1 1 0]]

EIGENVECTOR_CENTRALITY:
 {0: 0.5773502691896258, 1: 0.5773502691896258, 2: 0.5773502691896258}
EIGENVALUES: [-1.  2. -1.]

EIGENVECTORS:
 [[-0.8165  0.5774  0.2265]
 [ 0.4082  0.5774 -0.7926]
 [ 0.4082  0.5774  0.5661]]
LENGTH OF EIGEN VECTORS: [1. 1. 1.]

Analytic solution

Source: https://www.emathhelp.net/en/calculators/linear-algebra/eigenvalue-and-eigenvector-calculator/

Note: 1/sqrt(3)=0.577350

Example: undirected

  • For directed graphs this is “left” eigenvector centrality which corresponds to the in-edges in the graph. For out-edges eigenvector centrality first reverse the graph with G.reverse().
Code
# Generate graph
import networkx as nx
G = nx.DiGraph()
G.add_nodes_from([0,1,2,3,4])
G.add_edges_from([(0, 1), (0, 2), (0,3), (0,4),(1,0),(2,3)])
nx.draw(G,with_labels=True)


# ADJACENCY MATRIX
A=nx.adjacency_matrix(G).todense().T #TRANSPOSE MAKES IT IN-DEGREE ORIENTS ROWS=IN
print("Adjacency matrix\n",A)

# METHOD-1: NETWORKX EIGENVECTOR_CENTRALITY
print("\nEIGENVECTOR_CENTRALITY:\n",nx.eigenvector_centrality(G))

# METHOD-2: COMPUTE FROM "SCRATCH"
print("EIGENVALUES:",np.linalg.eig(A)[0])
eVect=np.array(np.linalg.eig(A)[1])
print("\nEIGENVECTORS:\n",np.round(eVect,4))
print("LENGTH OF EIGEN VECTORS:",
np.sqrt(np.sum((eVect)**2,axis=0))**0.5)
Adjacency matrix
 [[0 1 0 0 0]
 [1 0 0 0 0]
 [1 0 0 0 0]
 [1 0 1 0 0]
 [1 0 0 0 0]]

EIGENVECTOR_CENTRALITY:
 {0: 0.35355406494349306, 1: 0.35355406494349306, 2: 0.35355406494349306, 3: 0.7071054324835365, 4: 0.35355406494349306}
EIGENVALUES: [ 0.  0.  0.  1. -1.]

EIGENVECTORS:
 [[ 0.      0.      0.      0.3536 -0.5   ]
 [ 0.      0.      0.      0.3536  0.5   ]
 [ 0.      0.      0.      0.3536  0.5   ]
 [ 1.     -1.      0.      0.7071  0.    ]
 [ 0.      0.      1.      0.3536  0.5   ]]
LENGTH OF EIGEN VECTORS: [1. 1. 1. 1. 1.]

Limitations

Eigencentrality works best for undirected graphs because they always yield a symmetric matrix with a clear, guaranteed principal eigenvector, whereas directed graphs can produce asymmetric matrices where centrality scores fail to properly propagate backward from “dead ends” or sinks.

  • Localization in networks with large hubs, nearly all the centrality mass can concentrate on the hub and its neighbors, leaving the rest of the network with scores near zero
  • Directed graphs nodes with no incoming edges get a score of exactly 0, and they pass that zero along, so entire regions of a DAG can score 0 (motivates Katz centrality, which adds a baseline score \(\beta\) to every node)
  • Disconnected graphs scores are only meaningful within a single connected component; the leading eigenvector concentrates on one component
  • Convergence power iteration can converge slowly (or fail) on some graphs, e.g., bipartite structures where \(|\lambda_1| = |\lambda_2|\)
  • No cross-network comparison scores are normalized per-graph, so values are not comparable across different networks

Summary

  • Eigenvector centrality scores nodes by the importance of their neighbors, not just their count
  • Mathematically the leading eigenvector of the adjacency matrix, \(A\mathbf{x} = \lambda_{\max}\mathbf{x}\)
  • Easy to compute (nx.eigenvector_centrality), and the basis for Katz centrality and PageRank
  • Best suited to connected, undirected networks; use Katz/PageRank for directed graphs