IndianTechnoEra: Discrete Mathematics For AIML - Chapter 7 Matrices in Discrete Structures

Chapter 7 — Matrices in Discrete Structures

This chapter covers matrices used in discrete mathematics, particularly for representing graphs, networks, and connections, which are foundational for Graph Neural Networks (GNNs) and network analysis in AI & ML.

7.1 Adjacency Matrices

An adjacency matrix is a square matrix used to represent a finite graph. The element A[i][j] is 1 if there is an edge from vertex i to vertex j, and 0 otherwise. AI/ML Context: Represents connections in graphs for GNNs, social networks, and knowledge graphs.

# Python example using NumPy
import numpy as np

# Graph with 3 nodes: 0,1,2
adj_matrix = np.array([
    [0, 1, 1],  # Node 0 connected to 1 and 2
    [1, 0, 0],  # Node 1 connected to 0
    [1, 0, 0]   # Node 2 connected to 0
])

print(adj_matrix)

7.2 Incidence Matrices

Incidence matrices describe relationships between vertices and edges. Rows represent vertices, columns represent edges, and entries indicate whether a vertex is incident to an edge. AI/ML Context: Useful for network connectivity analysis and optimization problems.

# Example for graph with 3 nodes and 2 edges
# Edge1: 0-1, Edge2: 0-2
inc_matrix = np.array([
    [1, 1],  # Node 0
    [1, 0],  # Node 1
    [0, 1]   # Node 2
])

print(inc_matrix)

7.3 Matrix Operations for Graphs

Matrices allow computations over graphs using algebraic operations:

• Matrix multiplication: Find number of paths of certain length between nodes.
• Transpose: Reverse direction of edges in directed graphs.
• Element-wise operations: Weight adjustment or masking connections.

# Number of paths of length 2
paths_len2 = adj_matrix @ adj_matrix
print(paths_len2)

7.4 ML Use Case: Graph Representation in AI/ML

• Graph Neural Networks (GNNs) use adjacency matrices to propagate node features.
• Connectivity and network analysis for social networks or recommendation systems.
• Knowledge graph embeddings for semantic relationships.
• Graph-based clustering and community detection.

7.5 Practical Python Implementation

import networkx as nx
import numpy as np

# Create a simple undirected graph
G = nx.Graph()
G.add_edges_from([(0,1), (0,2), (1,2)])

# Adjacency matrix
adj = nx.adjacency_matrix(G).todense()
print("Adjacency Matrix:\n", adj)

# Incidence matrix
inc = nx.incidence_matrix(G, oriented=False).todense()
print("Incidence Matrix:\n", inc)

7.6 Why Matrices in Discrete Structures Matter in AI/ML

• Represent and manipulate graph structures efficiently.
• Enable graph-based feature propagation in neural networks.
• Support connectivity and network analysis tasks for AI applications.
• Bridge discrete mathematics with practical ML implementations.

7.7 Exercises

1. Create the adjacency matrix for a given directed graph with 4 nodes.
2. Compute the number of paths of length 3 using matrix multiplication.
3. Implement a simple GNN layer using adjacency matrix and node features in Python.

Hints / Solutions

1. Use NumPy arrays for adjacency and incidence matrices.
2. Matrix powers give paths of specific lengths.
3. GNN layer: output = ReLU(adj_matrix @ features @ weights)

7.8 Further Reading & Videos

• NetworkX documentation — Python library for graphs and matrices
• Graph Neural Networks (GNNs) tutorials — PyTorch Geometric or DGL
• Discrete Mathematics and its Applications by Kenneth H. Rosen
• Video lectures on adjacency matrices and graph algorithms

Next Chapter: Graph Algorithms & Traversals — explore BFS, DFS, shortest paths, and their applications in AI & ML.