Matrices are abstract structures like graphs that have applications in many scientific fields. They form the foundation of linear algebra, which is widely used in artificial intelligence algorithms and machine learning. In Olympiads, matrices are used in complex algorithms like FFT (Fast Fourier Transform), and familiarity with them is beneficial for an Olympiad student.
In this chapter, we will briefly introduce matrices and then examine the relationship between matrices and graphs. Using this connection, we will develop fast algorithms for solving several problems.
Any rectangular arrangement of real numbers consisting of a number of rows and columns is called a matrix. Each real number located in a matrix is called an entry of that matrix.
\(\begin{equation*} A = \begin{bmatrix} 12 & 78 & -120 \\ 3.7 & -809 & 5 \end{bmatrix} \end{equation*}\) \(\begin{equation*} B = \begin{bmatrix} 1 & 3 \\ 4 & 2 \end{bmatrix} \end{equation*}\) \(\begin{equation*} C = \begin{bmatrix} -0.5 & -90 \\ 0 & 4.09 \\ 5 & 6 \\ 92 & 37 \end{bmatrix} \end{equation*}\)
Key points:
- Maintained RST heading syntax with ----
underline
- Preserved original LaTeX code blocks without any changes
- Translated Persian text faithfully while keeping:
Technical terms like "درایه" → "entry"
Mathematical notation unchanged
Paragraph structure identical to original
Bold formatting kept for emphasized terms
A matrix with m columns and n rows is called an order of n × m.
To add two matrices, first we must ensure they have the same number of rows and columns (the number of rows doesn't need to equal the number of columns). Then, each entry in matrix A is added to its corresponding entry in matrix B to create the corresponding entry in matrix C. The subtraction operation follows the same method.
\(\begin{equation*} \begin{bmatrix} 2 & 4 \\ 1 & 3 \end{bmatrix} + \begin{bmatrix} 3 & 2 \\ 4 & 1 \end{bmatrix} = \begin{bmatrix} 5 & 6 \\ 5 & 4 \end{bmatrix} \end{equation*}\)
\(\begin{equation*} \begin{bmatrix} 37 & 7 \\ 0 & 3 \end{bmatrix} - \begin{bmatrix} 6 & 13 \\ 2 & -5 \end{bmatrix} = \begin{bmatrix} 31 & -6 \\ -2 & 8 \end{bmatrix} \end{equation*}\)
To multiply matrices, first note that if matrix A has n rows and m columns, matrix B must have m rows and z columns. In this case, the resulting matrix C—the product of the two matrices—will have n rows and z columns. The entry \(c_{ij}\) equals the sum of \(a_{ik} × b_{kj}\), where k is a natural number with a maximum value of m.
\(\begin{equation*} \begin{bmatrix} 4 & 2 & 3 \\ 0 & 3 & -1 \end{bmatrix} \begin{bmatrix} 7 \\ -5 \\ 10 \end{bmatrix} = \begin{bmatrix} 48 \\ -25 \end{bmatrix} \end{equation*}\)
When a real number k is multiplied by a matrix, all entries of the matrix are multiplied by k.
\(\begin{equation*} 5 \begin{bmatrix} 0 & 1 \\ 2 & 3 \end{bmatrix} = \begin{bmatrix} 0 & 5 \\ 10 & 15 \end{bmatrix} \end{equation*}\)