.. _special_matrices: Some Special Matrices ===================== **Adjacency Matrix** -------------------- The adjacency matrix is one of the most important tools for analyzing graphs. This matrix is defined as follows for a graph with *n* vertices: .. math:: A = [a_{ij}]_{n \times n} \quad \text{where} \quad a_{ij} = \begin{cases} 1 & \text{if there is an edge between vertices } i \text{ and } j \\ 0 & \text{otherwise} \end{cases} Key properties of the adjacency matrix: - If the graph is undirected, the adjacency matrix will be **symmetric**. - If the graph is directed, the entry :math:`a_{ij}` equals the number of edges **from** vertex :math:`i` **to** vertex :math:`j`. - If the graph is weighted, :math:`a_{ij}` represents the **weight** of the edge between vertices :math:`i` and :math:`j`. Example adjacency matrix for an undirected graph: .. code-block:: python # Adjacency matrix for graph 5.3 adjacency_matrix = [ [0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 0], [1, 1, 0, 0] ] .. figure:: images/adjacency_matrix.png :width: 200px :align: center :caption: Adjacency matrix of the graph in Figure 5.3 **Incidence Matrix** -------------------- The incidence matrix represents connections between vertices and edges. For a graph with *n* vertices and *m* edges, it is an :math:`n \times m` matrix defined as: .. math:: B = [b_{ij}]_{n \times m} \quad \text{where} \quad b_{ij} = \begin{cases} 1 & \text{if vertex } i \text{ is incident to edge } j \\ 0 & \text{otherwise} \end{cases} Example incidence matrix: .. code-block:: python # Incidence matrix for graph 5.3 incidence_matrix = [ [1, 1, 0, 0], # Vertex 1 [1, 0, 1, 1], # Vertex 2 [0, 1, 1, 0], # Vertex 3 [0, 0, 0, 1] # Vertex 4 ] .. note:: In directed graphs, the incidence matrix uses :math:`-1` and :math:`1` to indicate edge direction. Zero Matrix ----------- A matrix where all entries are zero. :math:`\begin{equation*} A = \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix} \end{equation*}` Row Matrix ------------ A matrix that has only one row. :math:`\begin{equation*} A = \begin{bmatrix} 37 & 3 & 16 & -0.5 & 13 \end{bmatrix} \end{equation*}` Column Matrix ------------- A matrix that has only one column. :math:`\begin{equation*} A = \begin{bmatrix} 37 \\ 4 \\ -5 \\ 3 \\ 0 \end{bmatrix} \end{equation*}` Square Matrix ------------- A matrix where the number of rows is equal to the number of columns. :math:`\begin{equation*} A = \begin{bmatrix} 37 & 3 \\ 5 & 23 \end{bmatrix} \end{equation*}` Diagonal Matrix --------------- A special type of square matrix where all entries above and below the main diagonal are zero. :math:`\begin{equation*} A = \begin{bmatrix} 9 & 0 & 0 \\ 0 & -4 & 0 \\ 0 & 0 & -1 \end{bmatrix} \end{equation*}` Scalar Matrix ------------- A diagonal matrix in which the entries on the main diagonal are equal. :math:`\begin{equation*} A = \begin{bmatrix} 37 & 0 \\ 0 & 37 \end{bmatrix} \end{equation*}` Identity Matrix --------------- A scalar matrix where the entries on the diagonal are equal to 1. This matrix of order n × n is denoted by :math:`I_n`. :math:`\begin{equation*} A = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \end{equation*}` Symmetric Matrix ---------------- A square matrix where the element in row i and column j equals the element in row j and column i. In other words: :math:`a_{ji}` = :math:`a_{ij}`. :math:`\begin{equation*} A = \begin{bmatrix} 1 & 3 & 37 & 0 \\ 3 & 2 & 23 & -5 \\ 37 & 23 & 3 & 66 \\ 0 & -5 & 66 & 4 \end{bmatrix} \end{equation*}` Idempotent Matrix ----------------- A square matrix for which there exists a power k such that :math:`A^k = A` is called an idempotent matrix. Transpose Matrix ---------------- The transpose matrix is constructed from another matrix. If we consider matrix A with n rows and m columns, the entry :math:`a^{T}_{ij}` of the transpose matrix created from A (denoted as :math:`A^T`) with m rows and n columns equals the entry :math:`a_{ji}` of matrix A. :math:`\begin{equation*} A = \begin{bmatrix} 1 & 2 & 0 \\ 3 & -1 & -2 \\ 4 & 0 & 5 \end{bmatrix} \end{equation*}` :math:`\begin{equation*} A^T = \begin{bmatrix} 1 & 3 & 4 \\ 2 & -1 & 0 \\ 0 & -2 & 5 \end{bmatrix} \end{equation*}` Triangular Matrix ----------------- A special type of square matrix. Triangular matrices are divided into two categories: upper triangular and lower triangular. An upper triangular matrix is defined as a matrix where all entries below the main diagonal are zero, and a lower triangular matrix is one where all entries above the main diagonal are zero. Adjugate Matrix --------------- The adjugate matrix is constructed from another matrix. If we consider matrix A, to obtain the entry :math:`a_{ij}` of the adjugate matrix, we first construct matrix B by removing row :math:`i` and column :math:`j` from matrix A. Then, the value of :math:`a_{ij}` is equal to the determinant of matrix B. :math:`\begin{equation*} A = \begin{bmatrix} 1 & 2 & 0 \\ 3 & -1 & -2 \\ 4 & 0 & 5 \end{bmatrix} \end{equation*}` :math:`\begin{equation*} B = \begin{bmatrix} -7 & 7 & -4 \\ 10 & 5 & -8 \\ 4 & 2 & -7 \end{bmatrix} \end{equation*}` .. The code blocks and math sections are kept unchanged as per instructions. Cofactor Matrix --------------- The cofactor matrix is constructed from another matrix, assumed to be matrix A. The entry in row :math:`i` and column :math:`j` of the cofactor matrix equals :math:`a_{ij}` multiplied by :math:`-1^{i + j}`. :math:`\begin{equation*} A = \begin{bmatrix} 37 & 8 & 6 \\ 11 & 0 & 7 \end{bmatrix} \end{equation*}` :math:`\begin{equation*} A' = \begin{bmatrix} 37 & -8 & 6 \\ -11 & 0 & -7 \end{bmatrix} \end{equation*}` Adjoint Matrix -------------- The adjoint matrix refers to the transpose of the cofactor matrix. Inverse Matrix ------------- Matrix B is called the inverse of matrix A if their product equals the identity matrix (A × B = I). The inverse of a matrix is equal to the adjugate matrix of its cofactor matrix. :math:`\begin{equation*} A = \begin{bmatrix} 2 & 1 \\ 5 & 3 \end{bmatrix} \end{equation*}` :math:`\begin{equation*} A' = \begin{bmatrix} 3 & -1 \\ -5 & 2 \end{bmatrix} \end{equation*}`