Computational Linear Algebra II

Graphs can be represented as matrices, which is particularly useful in various fields such as computer science, network analysis, and discrete mathematics due to their ability to model problems using linear algebra techniques.

A graph G = (V, E) consists of two main components: V, which represents the set of vertices (or nodes), and E, which signifies the set of edges (or connections) that link these vertices.

The adjacency matrix is a square matrix used to represent a finite graph; the entries of the matrix indicate the presence or absence of edges between the vertices. If the graph is weighted, the entries represent edge weights instead of binary values.

Key graph properties such as in-degree (the number of edges incoming to a vertex) and out-degree (the number of edges outgoing from a vertex) can be computed directly from the adjacency matrix, facilitating efficient analysis and manipulation of graph data.

Symmetric matrices are utilized to represent undirected graphs, where the edge connections have no direction, allowing for a simplified structure in the adjacency representation.

Edge-weighted graphs illustrate varying strengths of connections between vertices, which can be visually represented as images, aiding in the understanding of the relationships and interactions within the graph's structure.

Example of an Adjacency Matrix

For a simple graph with vertices A, B, and C, and edges (A, B) and (B, C):

• Vertices: V = {A, B, C}

• Edges: E = {(A, B), (B, C)}

The corresponding adjacency matrix A would look like:

A = \begin{pmatrix}
0 & 1 & 0 \
1 & 0 & 1 \
0 & 1 & 0
\end{pmatrix}

Flows on Graphs

Graphs can represent flows of mass or resources through networks, providing insights into transport, communication, and ecological models.

Conserving adjacency (stochastic) matrices are crucial in these contexts, as they preserve mass by ensuring that the sum of the rows equals 1, reflecting a conservation principle within the flow.

The degree matrix D is a diagonal matrix where each element signifies the sum of the weights of edges connected to each vertex, providing an overview of the connectivity of the vertices within the graph.

The Laplacian matrix L = D - A, where A is the adjacency matrix, plays a critical role in graph analysis, enabling the evaluation of properties such as the number of connected components and the structure of flow within the graph.

Example Code - Calculating Laplacian Matrix

Here's a Python code example using NumPy to compute the Laplacian matrix from an adjacency matrix:

import numpy as np

# Define the adjacency matrix A
a = np.array([[0, 1, 0],
              [1, 0, 1],
              [0, 1, 0]])

# Calculate the degree matrix D
d = np.diag(np.sum(a, axis=1))

# Calculate the Laplacian matrix L
l = d - a
print("Laplacian Matrix:")
print(l)

Matrix Classes

Symmetric matrix: Defined as a matrix that is equal to its transpose, which has important implications in various mathematical fields, such as physics and statistics.

Sparse matrix: Characterized by the majority of its elements being zero, these matrices are essential in large-scale computations where memory efficiency is critical.

Stochastic matrix: This matrix features non-negative elements with each row summing to 1, maintaining mass preservation—key in probability and flow-related applications.

Doubly-stochastic matrix: A particular type where both rows and columns sum to 1, essential in applications involving bidirectional flow conservation between pairs of entities.

Uses of Matrices

Matrices are fundamental in encoding linear functions and possess applications that range from geometric transformations to graphical representations of connectivity in networks.

They can model complex discrete problems effectively using continuous mathematics, thus allowing for insights into various behaviors modeled by linear relationships.