Déterminants en algèbre linéaire

Algèbre Linéaire

Rappels d'algèbre linéaire

• Le déterminant est une valeur scalaire qui peut être calculée à partir d'une matrice carrée.
• Il est noté $\det(A)$ ou $|A|$ pour une matrice carrée $A$ de taille $n \times n$.
• Pour $n = 1$, si $A = (a_{11})$, alors $\det(A) = a_{11}$.
• Pour $n = 2$, si $A = \begin{pmatrix} a_{11} & a_{12} \ a_{21} & a_{22} \end{pmatrix}$, alors $\det(A) = a_{11}a_{22} - a_{12}a_{21}$.
• Pour $n \geq 2$, le déterminant est défini par récurrence comme $\det(A) = \sum_{i=1}^{n} (-1)^{i+1} a_{i1} \det(A_{i1})$, où $A_{i1}$ est la sous-matrice obtenue en supprimant la $i$-ème ligne et la première colonne.
• On peut développer le déterminant par rapport à n'importe quelle colonne $j$ avec la formule $\det(A) = \sum_{i=1}^{n} (-1)^{i+j} a_{ij} \det(A_{ij})$.
• On peut développer le déterminant par rapport à n'importe quelle ligne $i$ avec la formule $\det(A) = \sum_{j=1}^{n} (-1)^{i+j} a_{ij} \det(A_{ij})$.

Propriétés du déterminant

• La transposition d'une matrice ne change pas son déterminant: $\det(A^T) = \det(A)$.
• Le déterminant du produit de deux matrices, c'est le produit de leur déterminant: $\det(AB) = \det(A) \det(B)$.
• Le déterminant de l'inverse d'une matrice est l'inverse de son déterminant: $\det(A^{-1}) = \frac{1}{\det(A)}$.
• Si $A$ a deux lignes ou colonnes identiques, alors $\det(A) = 0$.
• L'échange de deux lignes ou colonnes de $A$ change le signe du déterminant.
• Multiplier une ligne ou colonne de $A$ par un scalaire $\lambda$ multiplie le déterminant par $\lambda$.
• Le déterminant est invariant si on ajoute à une ligne (ou colonne) une combinaison linéaire des autres lignes (ou colonnes).
• Une matrice $A$ est inversible si et seulement si $\det(A) \neq 0$.

Les valeurs propres et vecteurs propres

• Un scalaire $\lambda \in \mathbb{K}$ est une valeur propre de $A$, une matrice carrée de taille $n \times n$, s'il existe un vecteur non nul $v \in \mathbb{K}^n$ tel que $Av = \lambda v$.
• Le vecteur $v$ est appelé vecteur propre de $A$ associé à la valeur propre $\lambda$.

Comment trouver les valeurs propres?

• Les valeurs propres de $A$ sont trouvées en résolvant l'équation caractéristique: $\det(A - \lambda I) = 0$, où $I$ est la matrice identité de taille $n \times n$.
• Le polynôme $P(\lambda) = \det(A - \lambda I)$ est appelé polynôme caractéristique de $A$.
• Les racines de ce polynôme sont les valeurs propres de $A$.

Comment trouver les vecteurs propres?

• Les vecteurs propres associés à une valeur propre $\lambda$ sont les solutions du système linéaire $(A - \lambda I)v = 0$.
• L'ensemble des vecteurs propres associés à une valeur propre $\lambda$, augmenté du vecteur nul, forme l'espace propre $E_\lambda$.

Diagonalisation

• Une matrice $A \in M_n(\mathbb{K})$ est diagonalisable s'il existe une matrice inversible $P \in M_n(\mathbb{K})$ et une matrice diagonale $D \in M_n(\mathbb{K})$ telles que $A = PDP^{-1}$.
• La matrice $P$ est la matrice de passage et ses colonnes sont formées par les vecteurs propres de $A$.
• La matrice $D$ est une matrice diagonale dont les éléments diagonaux sont les valeurs propres de $A$.

Quand est-ce qu'une matrice est diagonalisable?

• Une matrice $A \in M_n(\mathbb{K})$ est diagonalisable si et seulement si la somme des dimensions des espaces propres de $A$ est égale à $n$: $\sum_{\lambda \in \text{Spec}(A)} \dim(E_\lambda) = n$.
• Ici, $\text{Spec}(A)$ est l'ensemble des valeurs propres de $A$.

Théorème spectral

• Si $A$ est une matrice symétrique réelle (i.e., $A = A^T$ et $A \in M_n(\mathbb{R})$), alors $A$ est diagonalisable.
• Il existe alors une matrice orthogonale $P$ telle que $A = PDP^{-1} = PDP^T$, où $D$ est une matrice diagonale dont les éléments diagonaux sont les valeurs propres de $A$.
• Les colonnes de $P$ sont les vecteurs propres de $A$, et forment une base orthonormée de $\mathbb{R}^n$.

Électricité Statique

Charge électrique

Friction

• Deux objets neutres sont frottés ensemble.
• Des électrons sont transférés d'un objet à l'autre.
• Un objet devient chargé positivement, l'autre négativement.
• Exemple: Frotter un ballon sur les cheveux; marcher avec des chaussettes sur un tapis.

Conduction

• Un objet chargé touche un objet neutre.
• Des électrons sont transférés entre les objets.
• L'objet neutre prend la même charge que l'objet chargé.
• Exemple: Toucher un générateur de Van de Graaff.

Polarisation

• Un objet chargé est approché d'un objet neutre.
• Les charges à l'intérieur de l'objet neutre se réarrangent.
• Un côté de l'objet neutre devient légèrement positif/négatif.
• L'objet neutre reste globalement neutre.
• Exemple: Tenir une tige chargée près d'un mur.

Force

Loi de coulomb

• La force entre deux objets chargés est proportionnelle à la quantité de charge sur chaque objet.
• La force est inversement proportionnelle au carré de la distance entre les objets.
• La force est attractive pour les charges opposées et répulsive pour les charges similaires.

$$ F = k \frac{q_1 q_2}{r^2} $$

• $F$ = Force (N)
• $k$ = Constante de Coulomb = $8.99 \times 10^9 \frac{N \cdot m^2}{C^2}$
• $q_1$ = Charge sur l'objet 1 (C)
• $q_2$ = Charge sur l'objet 2 (C)
• $r$ = Distance entre les objets (m)

Champ électrique

• Un objet chargé crée un champ électrique autour de lui.
• Le champ électrique exerce une force sur tout autre objet chargé à l'intérieur du champ.
• Les lignes de champ électrique pointent dans la direction de la force sur une charge de test positive.

$$ E = \frac{F}{q} $$

• $E$ = Intensité du champ électrique (N/C)
• $F$ = Force (N)
• $q$ = Charge (C)

Le courant

Courant électrique

• Le débit de charge électrique.
• Le courant conventionnel est défini comme le flux de charge positive.
• Les électrons circulent en réalité dans la direction opposée.

$$ I = \frac{Q}{t} $$

• $I$ = Courant (A)
• $Q$ = Charge (C)
• $t$ = Temps (s)

Tension

• La différence de potentiel électrique entre deux points.
• La quantité de travail nécessaire pour déplacer une charge unitaire entre deux points.

$$ V = \frac{W}{Q} $$

• $V$ = Tension (V)
• $W$ = Travail (J)
• $Q$ = Charge (C)

Résistance

• Une mesure de la difficulté pour le courant de circuler à travers un matériau.
• Opposition à la circulation du courant électrique.

$$ R = \frac{V}{I} $$

• $R$ = Résistance ($\Omega$)
• $V$ = Tension (V)
• $I$ = Courant (A)

Loi d'Ohm

• La tension aux bornes d'une résistance est proportionnelle au courant qui la traverse.

$$ V = IR $$

• $V$ = Tension (V)
• $I$ = Courant (A)
• $R$ = Résistance ($\Omega$)

Circuits

Circuits en série

• Les composants sont connectés l'un après l'autre sur un seul chemin.
• Le courant est le même à travers tous les composants.
• La résistance totale est la somme des résistances individuelles.
• La tension est divisée entre les composants.

Circuits parallèles

• Les composants sont connectés dans plusieurs chemins.
• La tension est la même à travers tous les composants.
• Le courant total est la somme des courants individuels.
• La résistance totale est inférieure à la plus petite résistance individuelle.

Puissance

• Le taux auquel l'énergie électrique est convertie en d'autres formes d'énergie.

$$ P = IV = I^2R = \frac{V^2}{R} $$

• $P$ = Puissance (W)
• $I$ = Courant (A)
• $V$ = Tension (V)
• $R$ = Résistance ($\Omega$)

Complexité Algorithmique

Quoi?

• La complexité algorithmique mesure le temps (complexité temporelle) et l'espace (complexité spatiale) requis par un algorithme pour résoudre un problème d'une taille donnée.
• Complexité temporelle : Temps nécessaire à un algorithme pour s'exécuter en fonction de la longueur de l'entrée.
• Complexité spatiale : Quantité d'espace mémoire requis par l'algorithme en fonction de la longueur de l'entrée.
• La notation Big O est la manière la plus courante d'exprimer la complexité algorithmique. Elle décrit le scénario le pire en termes de performances d'un algorithme.

Pourquoi?

• Comprendre la complexité algorithmique est crucial pour choisir le bon algorithme, prédire les performances, optimiser le code et assurer l'évolutivité.
• Choisir le bon algorithme : Différents algorithmes ont différentes complexités.
• Prédire les performances : Permet d'estimer les performances d'un algorithme à mesure que la taille des entrées augmente.
• Optimiser le code : En identifiant les points d'étranglement dans votre code, vous pouvez vous concentrer sur l'optimisation.
• Evolutivité : Aide à comprendre comment un algorithme s'adaptera à mesure que la taille des données augmente.

Comment?

Complexités courantes

• Les complexités Big O sont présentées de la plus rapide à la plus lente.

Comment déterminer la complexité

1. Identifier les opérations dominantes: Concentrez-vous sur les opérations effectuées le plus fréquemment à mesure que la taille de l'entrée augmente.
2. Compter les opérations: Déterminez comment le nombre d'opérations dominantes change avec la taille de l'entrée.
3. Exprimer en Big O: Utilisez la notation Big O pour exprimer la relation entre le nombre d'opérations et la taille de l'entrée.

Exemple

def find_element(arr, target):
    for element in arr: # O(n)
        if element == target: # O(1)
            return True
    return False

• Dans cet exemple, la boucle parcourt chaque élément du tableau, donc la complexité temporelle est O(n).
• Comprendre la complexité algorithmique est essentiel pour écrire du code efficace et évolutif.
• En considérant les exigences de temps et d'espace de vos algorithmes, vous pouvez prendre des décisions éclairées qui conduisent à de meilleures performances.