Introduction to Matrices

Matrices

Generalities

• A matrix represents a rectangular array of numbers arranged in rows and columns.
• Denoted as $A = (a_{ij})$ where:
  • $i$ is the row index
  • $j$ is the column index
  • $a_{ij}$ is the element in the $i$-th row and $j$-th column
  • $m \times n$ is the size of the matrix with $m$ rows and $n$ columns
• For example, $A = \begin{bmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \end{bmatrix}$ is a $2 \times 3$ matrix.
• Special matrices include:
  • Square matrix ($m = n$)
  • Row matrix ($m = 1$)
  • Column matrix ($n = 1$)
  • Zero matrix (all elements are zero)
  • Identity matrix (square matrix with 1 on the diagonal and 0 elsewhere)

Matrix Operations

• Addition is possible when two matrices A and B have the same size defined as $A + B = (a_{ij} + b_{ij})$
• Scalar Multiplication is possible when a matrix A can be multiplied by a scalar $c$ defined as $cA = (ca_{ij})$
• Multiplication is possible when the number of columns of A is equal to the number of rows of B
  • If A is an $m \times n$ matrix and B is an $n \times p$ matrix, then $AB$ is an $m \times p$ matrix.
  • Defined as $(AB){ij} = \sum{k=1}^{n} a_{ik}b_{kj}$
• Transpose involves interchanging rows and columns of a matrix A defined as $A^T = (a_{ji})$
• Inverse of a square matrix A is a matrix $A^{-1}$ such that $AA^{-1} = A^{-1}A = I$, where I is the identity matrix
  • Not all matrices have an invers
  • A matrix that has an inverse is called invertible or non-singular
  • A matrix that does not have an inverse is called singular

Determinant

• It's a scalar value computed from the elements of a square matrix A.
• Denoted as $\det(A)$ or $|A|$
• Calculated as:
  • For a $2 \times 2$ matrix: - $\det \begin{bmatrix} a & b \ c & d \end{bmatrix} = ad - bc$
  • For a $3 \times 3$ matrix: - $\det \begin{bmatrix} a & b & c \ d & e & f \ g & h & i \end{bmatrix} = a(ei - fh) - b(di - fg) + c(dh - eg)$
• Properties include:
  • $\det(A^T) = \det(A)$
  • $\det(AB) = \det(A) \det(B)$
  • $\det(A^{-1}) = \frac{1}{\det(A)}$

Systems of Linear Equations

• Representation:
  • A system of linear equations can be represented in matrix form as $Ax = b$, where:
    • A is the coefficient matrix
    • x is the vector of variables
    • b is the vector of constants
• Solving methods:
  • Gaussian elimination
  • Gauss-Jordan elimination
  • Matrix inversion
  • Cramer's rule
• Example:
  • $x + y = 3$
  • $2x - y = 0$
  • $\begin{bmatrix} 1 & 1 \ 2 & -1 \end{bmatrix} \begin{bmatrix} x \ y \end{bmatrix} = \begin{bmatrix} 3 \ 0 \end{bmatrix}$

Algorithmes de tri

Résumé

• Studying classical sorting algorithms, including insertion sort, selection sort, merge sort, and quick sort
• Description of operation, pseudo-code, example, complexity analysis, and comparison for each

Introduction

• Sorting is organizing a collection of elements in a specific order.
• Multiple sort algorithms have been developed
  • Each has its own advantages and disadvantages

Tri par insertion

• Algorithm that works by traversing the array from left to right
• Inserts each element in its place among the previous sorted elements

Pseudo-code

Pour i de 1 à n-1:
    key = arr[i]
    j = i - 1
    Tant que j >= 0 et arr[j] > key:
        arr[j+1] = arr[j]
        j = j - 1
    arr[j+1] = key

Exemple

• For the array [5, 2, 4, 6, 1, 3]:
  • [5, 2, 4, 6, 1, 3] (2 is inserted before 5)
  • [2, 5, 4, 6, 1, 3] (4 is inserted between 2 and 5)
  • [2, 4, 5, 6, 1, 3] (6 is already in place)
  • [2, 4, 5, 6, 1, 3] (1 is inserted at the beginning)
  • [1, 2, 4, 5, 6, 3] (3 is inserted between 2 and 4)
  • [1, 2, 3, 4, 5, 6]

Complexité

• Meilleur cas : $O(n)$ (tableau déjà trié)
• Cas moyen : $O(n^2)$
• Pire cas : $O(n^2)$ (tableau trié en ordre inverse)

Tri par sélection

Principe

• The algorithm consists of finding the smallest element of the array and swapping it with the first element
• Operation is then repeated for the rest of the array

Pseudo-code

Pour i de 0 à n-2:
    min_index = i
    Pour j de i+1 à n-1:
        Si arr[j] < arr[min_index]:
            min_index = j
    Si min_index != i:
        Echanger arr[i] et arr[min_index]

Exemple

• For the array [64, 25, 12, 22, 11]:
  • [11, 25, 12, 22, 64] (11 is the smallest, swapped with 64)
  • [11, 12, 25, 22, 64] (12 is the smallest, swapped with 25)
  • [11, 12, 22, 25, 64] (22 is the smallest, swapped with 25)
  • [11, 12, 22, 25, 64] (25 is already in place)

Complexité

• Meilleur cas : $O(n^2)$
• Cas moyen : $O(n^2)$
• Pire cas : $O(n^2)$

Tri fusion

Principe

• Sort algorithm based on the "divide to conquer" principle
• Divides the array into two halves, recursively sorts each half, and merges the two sorted halves.

Pseudo-code

Fonction tri_fusion(arr):
   Si len(arr)