Des articles

11.4 : Diagonalisation - Mathématiques


Soit (e=(e_1,ldots,e_n)) une base pour un espace vectoriel (n)-dimensionnel (V), et soit (Tin mathcal{L}(V) ). Ceci est fait pour souligner la dépendance sur la base (e).

En d'autres termes, nous avons que

[ [Tv]_e = [T]_e [v]_e, qquad ext{pour tout (vin V)}, ]

egin{équation*}
[v]_e = egin{bmatrix} v_1 vdots v_n end{bmatrix}
end{équation*}

est le vecteur de coordonnées pour (v= v_1 e_1 + cdots + v_n e_n) avec (v_iin mathbb{F}).

L'opérateur (T) est diagonalisable s'il existe une base (e) telle que ([T]_e) soit diagonale, c'est-à-dire s'il existe (lambda_1,ldots,lambda_n in mathbb{F}) tel que

egin{équation*}
[T]_e = egin{bmatrix} lambda_1 &&0 &ddots& 0&&lambda_n end{bmatrix}.
end{équation*}

Les scalaires (lambda_1,ldots,lambda_n) sont nécessairement des valeurs propres de (T), et (e_1,ldots,e_n) sont les vecteurs propres correspondants. Nous résumons cela dans la proposition suivante.

Proposition 11.4.1. (Tin mathcal{L}(V)) est diagonalisable si et seulement s'il existe une base ((e_1,ldots,e_n)) constitué entièrement de vecteurs propres de (T).

Nous pouvons reformuler cette proposition en utilisant les transformations de changement de base comme suit. Supposons que (e) et (f) soient des bases de (V) telles que ([T]_e) soit diagonale, et soit (S) le changement de transformation de base tel que ([v]_e=S[v]_f). Alors (S[T]_fS^{-1}=[T]_e) est diagonale.
Proposition 11.4.2. (Tin mathcal{L}(V)) est diagonalisable si et seulement s'il existe une matrice inversible (Sin mathbb{F}^{nfois n}) tel que
egin{équation*}
S [T]_f S^{-1} = egin{bmatrix} lambda_1 &&0 &ddots& 0&&lambda_n end{bmatrix},
end{équation*}
([T]_f) est la matrice pour (T) par rapport à une base arbitraire donnée (f=(f_1,ldots,f_n)).

D'autre part, le théorème spectral nous dit que (T) est diagonalisable par rapport à une base orthonormée si et seulement si (T) est normal. Rappeler que

egin{équation*}
[T^*]_f = [T]_f^*
end{équation*}
pour toute base orthonormée (f) de (V). Comme avant,
egin{équation*}
A^* = (overline{a}_{ji})_{ij=1}^n, qquad ext{for (A=(a_{ij})_{i,j=1}^n )},
end{équation*}

est la transposée conjuguée de la matrice (A). Lorsque (mathbb{F}=mathbb{R}), notez que (A^*=A^{T}) n'est que la transposée de la matrice, où (A^{T}=( a_{ji})_{i,j=1}^n).

La transformation de changement de base entre deux bases orthonormées est appelée unitaire dans le cas complexe et extbf{orthogonal} dans le cas réel. Soient (e=(e_1,ldots,e_n)) et (f=(f_1,ldots,f_n)) deux bases orthonormées de (V), et soit (U) la changement de matrice de base tel que ([v]_f=U[v]_e), pour tout (vin V). Puis

egin{équation*}
inner{e_i}{e_j} = delta_{ij} = inner{f_i}{f_j} = inner{Ue_i}{Ue_j}.
end{équation*}
Puisque cela vaut pour la base (e), il s'ensuit que (U) est unitaire si et seulement si
egin{equation} label{eq:unitary}
inner{Uv}{Uw} = inner{v}{w} quad ext{pour tout (v,win V)}. ag{11.4.1}
end{équation}

Cela signifie que les matrices unitaires préservent le produit interne. Les opérateurs qui préservent le produit intérieur sont souvent aussi appelés isométries. Les matrices orthogonales définissent également des isométries.

Par la définition de l'adjoint, (inner{Uv}{Uw}=inner{v}{U^*Uw}), et donc l'équation 11.4.1 implique que les isométries sont caractérisées par la propriété

egin{équation*}
egin{split}
U^*U &= I, qquad ext{pour le cas unitaire},
O^{T}O &= I, qquad ext{pour le cas orthogonal.}
end{split}
end{équation*}

L'équation (U^*U=I) implique que (U^{-1}=U^*). Pour les espaces de produits internes de dimension finie, l'inverse gauche d'un opérateur est également l'inverse droit, et ainsi

egin{array}{c} UU^* = I quad ext{si et seulement si} quad U^*U=I, ~~~~~~~~ OO^{T} = I quad text{si et seulement si} quad O^{T} O =I. ag{11.4.2} end{array}

Il est facile de voir que les colonnes d'une matrice unitaire sont les coefficients des éléments d'une base orthonormée par rapport à une autre base orthonormée. Les colonnes sont donc des vecteurs orthonormés dans (mathbb{C}^n) (ou dans (mathbb{R}^n) dans le cas réel). Par Condition (11.4.2), ceci est également vrai pour les lignes de la matrice.

Le théorème spectral nous dit que (T in mathcal{L}(V)) est normal si et seulement si ([T]_e) est diagonal par rapport à une base orthonormée (e) pour (V), c'est-à-dire s'il existe une matrice unitaire (U) telle que

egin{équation*}
UTU^* = egin{bmatrix} lambda_1 &&0 &ddots& 0&&lambda_n end{bmatrix}.
end{équation*}

Inversement, si une matrice unitaire (U) existe telle que (UTU^*=D) est diagonale, alors

egin{équation*}
TT^* - T^*T = U^*(Doverline{D}-overline{D}D)U=0
end{équation*}

puisque les matrices diagonales commutent, et donc (T) est normal. Résumons quelques-unes des définitions que nous avons vues dans cette section.

Définition 11.4.3. Étant donnée une matrice carrée (A in mathbb{F}^{n imes n}), on appelle

  1. symétrique si (A = A^{T}).
  2. Hermitien si (A = A^{*}).
  3. orthogonal si (A A^{T} = I).
  4. unitaire si (A A^{*} = I).

Notez que chaque type de matrice dans la définition 11.4.3 est un exemple d'opérateur normal. Un exemple d'opérateur normal (N) qui n'est ni hermitien ni unitaire est

[ N = i left[ egin{array}{cc} -1 & -1 - 1 & 1 end{array} ight] ]

Vous pouvez facilement vérifier que ( NN^* = N^*N ) et que (iN) est symétrique (non hermitien).

Exemple 11.4.4. Considérez la matrice
egin{équation*}
A = egin{bmatrice} 2 & 1+i 1-i & 3 end{bmatrice}
end{équation*}

de l'exemple 11.1.5~ ef{ex:hermitian}. Pour diagonaliser unitairement (A), il faut trouver une matrice unitaire (U) et une matrice diagonale (D) telles que (A=UDU^{-1}). Pour ce faire, nous devons d'abord trouver une base pour (mathbb{C}^{2}) qui se compose entièrement de vecteurs propres orthonormés pour l'application linéaire (Tin mathcal{L}(mathbb{C }^2)) défini par (Tv=Av), pour tout (vin mathbb{C}^2).

Pour trouver une telle base orthonormée, on commence par trouver les espaces propres de (T). Nous avons déjà déterminé que les valeurs propres de (T) sont (lambda_1=1) et (lambda_2=4), donc (D = egin{bmatrix} 1&0&4 end{bmatrix} ). Il s'ensuit que

egin{équation*}
egin{split}
mathbb{C}^2 &= kernel(T-I) oplus kernel(T-4I)
&= Span((-1-i,1)) oplus Span((1+i,2)).
end{split}
end{équation*}

Appliquez maintenant la procédure de Gram-Schmidt à chaque espace propre afin d'obtenir les colonnes de (U).
Ici,
egin{équation*}
egin{split}
A = UDU^{-1}
&= egin{bmatrix} frac{-1-i}{sqrt{3}} & frac{1+i}{sqrt{6}} frac{1}{sqrt{3} } & frac{2}{sqrt{6}}
end{bmatrice}
egin{bmatrice} 1&0 0&4 end{bmatrice}
egin{bmatrix} frac{-1-i}{sqrt{3}} & frac{1+i}{sqrt{6}} frac{1}{sqrt{3}} & frac{2}{sqrt{6}}
end{bmatrice}^{-1}
&= egin{bmatrix} frac{-1-i}{sqrt{3}} & frac{1+i}{sqrt{6}} frac{1}{sqrt{3} } & frac{2}{sqrt{6}}
end{bmatrice}
egin{bmatrice} 1&0 0&4 end{bmatrice}
egin{bmatrix} frac{-1+i}{sqrt{3}} & frac{1}{sqrt{3}} frac{1-i}{sqrt{6}} & frac{2}{sqrt{6}}
end{bmatrice}.
end{split}
end{équation*}

Comme application, notez qu'une telle décomposition diagonale nous permet de calculer facilement les puissances et l'exponentielle des matrices. A savoir, si ( A = UDU^{-1} ) avec (D) diagonale, alors on a

egin{équation*}
egin{split}
A^n &= (UDU^{-1})^n = U D^n U^{-1},
exp(A) &= sum_{k=0}^infty frac{1}{k!} A^k
= U left(sum_{k=0}^infty frac{1}{k!} D^k ight) U^{-1} = U exp(D) U^{-1}.
end{split}
end{équation*}

Exemple 11.4.5. Suite de l'exemple 11.4.4,
egin{équation*}
egin{split}
A^2 &= (UDU^{-1})^2 = UD^2 U^{-1} = U egin{bmatrix} 1&0&16end{bmatrix} U^*
= egin{bmatrice} 6& 5+5i 5-5i&11 end{bmatrice},[4mm]
A^n &= (UDU^{-1})^n = UD^n U^{-1} = U egin{bmatrix} 1&0&2^{2n}end{bmatrix} U^*
= egin{bmatrice} frac{2}{3}(1+2^{n-1})& frac{1+i}{3}(-1+2^{2n}) frac {1-i}{3}(-1+2^{2n})&
frac{1}{3}(1+2^{2n+1}) end{bmatrice},[4mm]
exp(A) &= Uexp(D) U^{-1} =U egin{bmatrice} e&0&e^4 end{bmatrice} U^{-1}
= frac{1}{3} egin{bmatrix} 2e+e^4 & e^4-e+i(e^4-e) e^4-e+i(ee^4) & e +2e^4 end{bmatrice}.
end{split}
end{équation*}


Diagonalisation de Cantor

Nous avons vu dans le Fun Fact Combien de rationnels ? que les nombres rationnels sont dénombrables, ce qui signifie qu'ils ont la même cardinalité que l'ensemble des nombres naturels.

Alors tous les ensembles infinis sont-ils dénombrables ?

Cantor a choqué le monde en montrant que les vrais nombres ne sont pas dénombrables & #8230 il y en a & #8220plus” que les nombres entiers ! Sa preuve était un usage ingénieux d'une preuve par contradiction. En fait, il a pu montrer qu'il existe des infinités de “tailles” différentes !

Suggestions de présentation :
Si vous avez le temps, montrez l'argument de diagonalisation de Cantor, qui se déroule comme suit. Si les réels étaient dénombrables, ils peuvent être mis en correspondance 1-1 avec les nombres naturels, nous pouvons donc les énumérer dans l'ordre donné par ces nombres naturels. Utilisez maintenant cette liste pour construire un nombre réel X qui diffère de chaque nombre de notre liste dans au moins une décimale, en laissant X différer du N-ième chiffre dans la N-ième décimale. (Un peu de soin doit être exercé pour s'assurer que X ne contient pas une chaîne infinie de 9’s.) Cela donne une contradiction, car la liste était censée contenir tous les nombres réels, y compris X. Par conséquent, d'où une correspondance 1-1 des réels avec les nombres naturels ne doit pas être possible.

Les mathématiques derrière le fait :
La théorie des ensembles dénombrables et indénombrables a été une grande surprise pour la communauté mathématique à la fin des années 1800.

Soit dit en passant, un argument similaire de “diagonalisation” peut être utilisé pour montrer que tout ensemble S et l'ensemble de tous les sous-ensembles S’s (appelé le ensemble de puissance de S) ne peut pas être placé dans une correspondance un à un. L'idée est la suivante : si une telle correspondance était possible, alors tout élément A de S a un sous-ensemble K(A) qui lui correspond. Construisez maintenant un nouveau sous-ensemble de S, appelez-le J, tel qu'un élément A soit dans J si et seulement si A n'est PAS dans K(A). Ce nouvel ensemble, par construction, ne peut jamais être K(A) pour tout A, car il diffère de chaque K(A) dans le “A-ème élément”. Donc, K(A) ne doit pas parcourir l'ensemble des puissances de A, donc la correspondance 1-1 affirmée ci-dessus ne doit pas être possible.

Cette preuve montre qu'il existe des ensembles infinis de nombreuses tailles différentes en considérant les nombres naturels et ses ensembles de puissance successifs ! La “size” d'un ensemble s'appelle sa cardinalité.

Comment citer cette page :
Su, Francis E., et al. “Diagonalisation de Cantor.” Faits amusants sur les mathématiques. <https://www.math.hmc.edu/funfacts>.

Les références:
Un texte classique sur l'analyse réelle est Walter Rudin’s Principes de l'analyse mathématique.


Si une matrice est diagonalisable, alors diagonalisez-la, $A=PDP^<-1>$ et appliquez la puissance à la diagonale

Les valeurs diagonales sont traitées individuellement.

$P=egin 0,85065 & -0,52573 & 0,57735 0,52573 & 0,85065 & 0,57735 0,00000 & 0,00000 & 0,57735fin$

$D= om de l'opérateur(0.82361, 0.37639,1)$ Je me rends compte que c'est une laideur numérique mais je n'ai pas de logiciel de manipulation symbolique à portée de main à partir de cet ordinateur. Cependant, les valeurs propres sont différentes, il s'agit donc d'une diagonalisation.

Cette définition satisfait l'exigence pour les racines que $(A^<1/p>)^p=A$ pour les matrices définies positives (comme avec $sqrt$ pour les scalaires).

De la même manière, vous pouvez définir des fonctions sur des matrices via leurs séries entières. Par exemple, $e^A=P exp(D)P^<-1>$ est parfaitement défini pour les matrices diagonalisables.

Les critères de convergence et le domaine de ces fonctions se généralisent et impliquent généralement des conditions pour les valeurs propres, la définition positive, la symétrie, l'ortogonalité, etc.

A noter que le terme racine carrée d'une matrice est parfois utilisé pour représenter une décomposition de Cholesky, qui fonctionne plutôt comme $A=LL^T$ où $L$ est une matrice triangulaire inférieure. Ce n'est pas la racine carrée au sens strict, mais cela fonctionne comme une pour certaines procédures numériques.


Le problème de l'arrêt

Le deuxième exemple que nous allons montrer d'une preuve par diagonalisation est le théorème d'arrêt, prouvé à l'origine par Alan Turing, qui dit qu'il existe certains problèmes que les ordinateurs ne peuvent pas résoudre, même s'ils disposent d'un espace et d'un temps illimités pour effectuer leurs calculs. Le modèle mathématique formel s'appelle une machine de Turing, mais pour simplifier, vous pouvez considérer les “machines de Turing” et les “algorithmes décrits par des mots” comme la même chose. Ou si vous le souhaitez, il peut s'agir de “programmes écrits en langage de programmation X.”. Nous utiliserons donc les trois mots “machine de Turing,” “algorithme,” et “programme” de manière interchangeable.

La preuve fonctionne en définissant réellement un problème et en prouvant qu'il ne peut pas être résolu. Le problème s'appelle le problème de l'arrêt, et c'est le problème de décider : étant donné un programme et une entrée à ce programme, s'arrêtera-t-il jamais de fonctionner lorsqu'il sera donné comme entrée ? Ce que je veux dire par “decide”, c'est que tout programme qui prétend résoudre le problème d'arrêt doit lui-même s'arrêter pour chaque entrée possible avec la bonne réponse. Un résolveur de problèmes « arrêtant » ne peut pas boucler à l'infini !

Nous allons donc d'abord donner la preuve standard que le problème de l'arrêt ne peut pas être résolu, puis nous inspecterons la forme de la preuve de plus près pour voir pourquoi elle est considérée comme un argument de diagonalisation.

Théorème: Le programme d'arrêt ne peut pas être résolu par les machines de Turing.

Preuve. Supposons au contraire qu'il s'agisse d'un programme qui résout le problème de l'arrêt. Nous l'utiliserons comme une boîte noire pour créer un nouveau programme que j'appellerai meta-, défini en pseudo-python comme suit.

En mots, meta- accepte en entrée le code source d'un programme, puis l'utilise pour dire si s'arrête (lorsqu'on lui donne son propre code source en entrée). Sur la base du résultat, il se comporte opposé de if s'arrête alors les méta-boucles infiniment et vice versa. C'est un peu méta, non ?

Maintenant, faisons quelque chose de fou : exécutons le méta sur lui-même ! c'est-à-dire courir

Donc méta. La question est quelle est la sortie de cet appel? Le métaprogramme utilise pour déterminer s'il s'arrête lorsqu'il est lui-même donné en entrée. Disons donc que la réponse à cette question est « oui, il s'arrête. » Ensuite, par la définition de méta-, le programme continue de boucler indéfiniment. Mais c'est un problème, car cela signifie que metaT(metaT) (qui est l'élément d'origine que nous avons exécuté) ne s'arrête en fait pas, ce qui contredit la réponse de ‘! De même, si dit que metaT(metaT) doit boucler à l'infini, cela provoquera l'arrêt de meta-, une contradiction. Cela ne peut donc pas être correct et le problème d'arrêt ne peut pas être résolu.

Ce théorème est profond car il dit que vous ne pouvez pas écrire un programme dans lequel vous pouvez toujours détecter des bogues dans d'autres programmes. Les boucles infinies ne sont qu'un type particulier de bogue.

Mais regardons de plus près et voyons pourquoi il s'agit d'une preuve par diagonalisation. La première chose dont nous devons nous convaincre est que l'ensemble de tous les programmes est dénombrable (c'est-à-dire qu'il y a une bijection de vers l'ensemble de tous les programmes). Cela ne devrait pas être si difficile à voir : vous pouvez lister tous les programmes dans l'ordre lexicographique, puisque l'ensemble de toutes les chaînes est dénombrable, puis rejeter tous ceux qui ne sont pas des programmes syntaxiquement valides. De même, l'ensemble de toutes les entrées, en réalité toutes les chaînes, est dénombrable.

La deuxième chose dont nous devons nous convaincre est qu'un problème correspond à une chaîne binaire infinie. Pour ce faire, nous limiterons notre attention aux problèmes de réponses oui/non, c'est-à-dire où le but du programme est de sortir un seul bit correspondant à oui ou non pour une entrée donnée. Ensuite, si nous listons toutes les entrées possibles dans l'ordre lexicographique croissant, un problème peut être représenté par la liste infinie de bits qui sont les sorties correctes de chaque entrée.

Par exemple, si le problème est de déterminer si une chaîne d'entrée binaire donnée correspond à un nombre pair, la représentation pourrait ressembler à ceci :

Bien sûr, tout dépend des détails de la façon dont on encode les entrées, mais le fait est que si vous le vouliez, vous pourriez définir tout cela avec précision. Plus important pour nous, nous pouvons représenter le problème de l'arrêt comme un infini tableau de bits. Si les colonnes du tableau sont tous des programmes (dans l'ordre lex), et les lignes du tableau correspondent aux entrées (dans l'ordre lex), alors le tableau aurait à l'entrée un 1 si s'arrête et un 0 sinon.

voici 1 si s'arrête et 0 sinon. Le tableau code les réponses au problème d'arrêt pour toutes les entrées possibles.

Maintenant, nous supposons pour des raisons de contradiction qu'un programme résout le problème d'arrêt, c'est-à-dire que chaque entrée de la table est calculable. Maintenant, nous allons construire les réponses sorties par méta- en retournant chaque bit de la diagonale du tableau. Le fait est que méta- correspond à certains ligne de la table, car il y a une chaîne d'entrée qui est interprétée comme le code source de meta-. Ensuite, nous soutenons que l'entrée de la table pour contredit sa définition, et nous avons terminé !

Ce sont donc deux des utilisations les plus médiatisées de la méthode de diagonalisation. C'est un excellent outil pour votre répertoire de démonstration.


Enseignants

Instructeur Assistant d'enseignement
Nom Miguel A. Lerma Léna Vaynberg
Bureau Lutte 203 Lutte B10
Téléphoner 1-8020 1-1956
E-mail [email protected] [email protected]
Heures de travail Sur rendez-vous lun-14h mer 19h-21h


Diagonalisation

Contenu
Partie I Arithmétique
Chapitre 1 Ensembles et commandes
1.1 Ensembles
1.2 Relations
1.3 Ordinaux
1.4 Cadres
Chapitre 2 Arithmétique formelle
2.1 Langage arithmétique avec le prédicat de vérité
2.2 Évaluation classique
2.3 L'arithmétique de la vérité et l'arithmétique de Peano
2.4 Modèles non standard d'arithmétique de la vérité
Chapitre 3 Fonctions récursives primitives et fonctions récursives
3.1 Fonctions récursives primitives
3.2 Quelques fonctions récursives primitives
3.3 Relations récursives primitives
3.4 Fonctions et relations récursives
Chapitre 4 Les nombres de Gödel et les fonctions associées
4.1 Les nombres de Gödel
4.2 Numéros de séquence
4.3 Récursivité du cours de la valeur
4.4 Quelques fonctions et relations syntaxiques
Chapitre 5 Définition arithmétique des fonctions récursives
5.1 Définition arithmétique
5.2 Composition et minimisation
5.3 Fonction bêta de Gödel
5.4 Opération récursive primitive
Chapitre 6 Indéfinissable de la vérité
6.1 Lemme diagonal
6.2 Théorème de Tarski
6.3 Théorème de Montague et théorème de McGee
6.4 Ensembles cohérents maximaux d'instances du schéma en T

Partie II Vérité
Chapitre 7 Théories de la hiérarchie
7.1 Problème de définition de la vérité
7.2 Hiérarchies linguistiques
7.3 Problème d'axiomatisation de la vérité
7.4 Théories axiomatiques des hiérarchies ascendantes et descendantes
Chapitre 8 Le schéma à trois valeurs fort de Kleene et le théorème du point fixe de Kripke
8.1 Le puissant schéma à trois valeurs de Kleene
8.2 Points fixes et prédicat de vérité
8.3 Théorème du point fixe
8.4 Une classification des phrases
Chapitre 9 Super-évaluation et points fixes minimaux
9.1 Précision des prédicats vagues
9.2 Schéma de super-évaluation
9.3 Une comparaison des points fixes minimaux
9.4 Points fixes et paradoxes
Chapitre 10 Périodicité des séquences de révision
10.1 Séquences de révision
10.2 Périodes de révision
10.3 Stabilité
10.4 Séquence de révision et paradoxes
Chapitre 11 Catégories et points fixes
11.1 Catégorisation des phrases
11.2 Description ensembliste de la catégorisation
11.3 Quasi-catégorie
11.4 Phrases catégoriques et phrases avec fondement
Chapitre 12 Relation de dépendance sémantique
12.1 Relation de dépendance
12.2 Dépendance et référence
12.3 Points fixes de l'opérateur de dépendance
12.4 Points fixes de dépendance et autres points fixes

Partie III Paradoxes
Chapitre 13 T-scheme et le menteur
13.1 T-schéma dans la construction du prédicat de vérité
13.2 Une caractérisation du menteur
13.3 Cercles vertueux et cercles vicieux
13.4 Élimination ou description des paradoxes
Chapitre 14 Degrés de paradoxe des paradoxes
14.1 Degrés de paradoxe
14.2 Une comparaison entre la carte du menteur et celle de Jourdain
14.3 Sauter les menteurs
14.4 Une caractérisation des Jump Liars
Chapitre 15 Paradoxes des cartes finies
15.1 Ensembles de phrases de cartes finies
15.2 Une généralisation des ensembles de phrases cartes finies
15.3 Les promenades et leur profondeur
15.4 Une caractérisation des paradoxes des cartes finies
Chapitre 16 Paradoxes booléens
16.1 Paradoxes booléens et leurs périodes de révision
16.2 Une construction de paradoxes booléens
16.3 Une caractérisation des paradoxes booléens
16.4 Structure des degrés de paradoxe des paradoxes booléens
Chapitre 17 Paradoxes et autoréférence
17.1 Paradoxes yabloesques
17.2 Paradoxes des cartes finies et paradoxes yabloesques
17.3 Non-autoréférence des paradoxes yabloesques
17.4 Autoréférence des systèmes de référence finis
Chapitre 18 Paradoxes et circularité
18.1 Paradoxes de la carte Transfinite
18.2 Le paradoxe de McGee
18.3 Une caractérisation des paradoxes des cartes transfinies et du paradoxe de McGee
18.4 Circularité des systèmes de référence finis
Bibliographie
Indice


Théorème de diagonalisation

Théorème. Une matrice $n imes n$ $A$ est diagonalisable si et seulement si elle a $n$ vecteurs propres linéairement indépendants. Dans ce cas, la matrice diagonale $D$ est similaire à $A$ et est donnée par egin étiqueter D= début lambda_1 & 0 & cdots & 0 0 & lambda_2 & cdots & 0 vdots & vdots & ddots& vdots 0 & 0 & cdots & lambda_n end finir où $lambda_1, ldots, lambda_n$ sont les valeurs propres de $A.$ Si $C$ est une matrice dont les colonnes sont des vecteurs propres linéairement indépendants de $A$, alors $D=C^<-1>A C. $

Corollaire. Soit $T$ une transformation linéaire donnée par $T(x)=A x$ où $A$ est une matrice carrée. Si $mathcal=(v_1, ldots,v_n)$ est une base propre pour $T$, avec $A v_i=lambda_i v_i$, alors le $mathcal$-matrice $D$ de $T$ donnée dans eqref est $ D=[ v_1, ldots, v_n]^<-1>A [ v_1, ldots, v_n]. $

Corollaire. Une matrice $A$ est diagonalisable si et seulement s'il existe une base propre pour $A.$ En particulier, si une matrice $nx n$ $A$ a $n$ valeurs propres distinctes, alors $A$ est diagonalisable.

Exemple. Soit $T : mathcal

_2à mathcal

_2$ la transformation linéaire définie par $ T(a_0+a_1 x+a_2x^2)=(a_0+a_1+a_2)+(a_1+a_2)x+a_2x^2. $ Montrer que $T$ n'est pas diagonalisable. La matrice de $T$ par rapport à la base usuelle $(, x, x^2)$ pour $mathcal

_2$ est facilement vu comme $ A= egin 1 & 1 & 1 0 & 1 & 1 0 & 0 & 1 end.$

Le polynôme caractéristique est $f_A(x)=-(x-1)^3$ puisque $A$ est le triangulaire supérieur. Donc $T$ n'a qu'une seule valeur propre (répétée) $lambda=1.$ Un polynôme non nul $g$ avec $g(x)=a_0+a_1 x+a_2 x^2$ est un vecteur propre si et seulement si $ étiqueter commencer 0 & 1 & 1 0 & 0 & 1 0 & 0 & 0 end commencera_0 a_1 a_2fin = commencer0 0 0fin. $

Donc $a_1=0$ et $a_2=0$, donc il n'y a qu'un seul vecteur propre linéairement indépendant pour $lambda=1.$ Donc $T$ n'est pas diagonalisable.


Structures discrètes appliquées

Dans cette section, présentez la plus grande opération de diviseur commun et présentez une famille importante de groupes concrets, les entiers modulo (n ext<.>)

Sous-section 11.4.1 Plus grands diviseurs communs

Nous commençons par un théorème sur la division entière qui est intuitivement clair. Nous laissons la preuve en exercice.

Théorème 11.4.1 . La propriété de division pour les entiers.

Si (m, nin mathbb ext<,>) (n>0 ext<,>) alors il existe deux entiers uniques, (q) (le quotient) et (r) (le reste), tels que (m = nq + r) et (0 leq r < n ext<.>)

Remarque 11.4.2.

La propriété division dit que si (m) est divisé par (n ext<,>) vous obtiendrez un quotient et un reste, où le reste est inférieur à (n ext<.>) Ceci est un fait que la plupart des élèves du primaire apprennent lorsqu'ils sont initiés à la division longue. En faisant le problème de division (1986 div 97 ext<,>) vous obtenez un quotient de 20 et un reste de 46. Ce résultat peut s'écrire soit (frac<1986><97>= 20+ frac<46><97>) ou (1986 = 97cdot 20 + 46 ext<.>) Cette dernière forme est la façon dont la propriété de division est normalement exprimée en mathématiques supérieures.

Nous rappelons maintenant au lecteur une terminologie interchangeable qui est utilisée lorsque (r=0 ext<,>) i. e., (a = b q ext<.>) Tout ce qui suit dit la même chose, juste de points de vue légèrement différents.

On utilise la notation (b mid a) si (b) divise (a ext<.>)

Par exemple (2mid 18) et (9mid 18) , mais (4 mid 18 ext<.>)

Attention : Ne confondez pas le symbole « divise » avec le symbole « divisé par ». Le premier est vertical tandis que le second est incliné. Notez cependant que l'instruction (2 mid 18) est liée au fait que (18/2) est un nombre entier.

Définition 11.4.4 . Plus grand diviseur commun.

Étant donné deux nombres entiers, (a) et (b ext<,>) pas tous les deux nuls, le plus grand diviseur commun de (a) et (b) est l'entier positif (g=gcd (a,b)) tel que (g mid a ext<,>) (gmid b ext<,>) et

Une façon un peu plus simple de penser à (gcd(a,b)) est comme le plus grand entier positif qui est un diviseur à la fois de (a) et de (b ext<.>) Cependant, notre définition est plus facile à appliquer pour prouver les propriétés des plus grands diviseurs communs.

Pour les petits nombres, un moyen simple de déterminer le plus grand diviseur commun consiste à utiliser la factorisation. Par exemple si on veut le plus grand commun diviseur de 660 et 350, on peut factoriser les deux entiers : (660=2^2cdot 3cdot 5cdot 11) et (350 = 2 cdot 5^2 cdot 7 ext<.>) Les facteurs uniques de 2 et 5 sont les seuls qui apparaissent dans les deux factorisations, donc le plus grand diviseur commun est (2cdot 5 =10 ext<.>)

Certaines paires d'entiers n'ont pas de diviseurs communs autres que 1. De telles paires sont appelées paires relativement premières.

Définition 11.4.5 . Relativement Premier.

Une paire d'entiers, (a) et (b ext<,>) sont relativement premiers si (gcd(a, b)=1)

Par exemple, (128=2^7) et (135=3^3cdot 5) sont relativement premiers. Notez que ni 128 ni 135 ne sont des nombres premiers. En général, (a) et (b) n'ont pas besoin d'être premiers pour être relativement premiers. Cependant, si vous commencez avec un nombre premier, comme 23, par exemple, il sera relativement premier à tout sauf à ses multiples. Ce théorème, que nous prouverons plus tard, généralise cette observation.

Théorème 11.4.6 .

Si (p) est un nombre premier et (a) est un entier tel que (p mid a) alors (gcd(a, p) = 1)

Sous-section 11.4.2 L'algorithme d'Euclide

Dès l'époque d'Euclide, on savait que la factorisation n'était pas le meilleur moyen de calculer les plus grands diviseurs communs.

L'algorithme d'Euclide est basé sur les propriétés suivantes du plus grand diviseur commun.

Pour calculer (gcd(a,b) ext<,>) on divise (b) en (a) et on obtient un reste (r) tel que (0leq r < lvert b vert ext<.>) Par la propriété ci-dessus, (gcd(a, b)= gcd(b, r) ext<.>) Nous répétons le processus jusqu'à ce que nous obtenions zéro pour un reste. Le dernier nombre différent de zéro qui est la deuxième entrée de nos paires est le plus grand diviseur commun. Ceci est inévitable car le deuxième nombre de chaque paire est plus petit que le précédent. Le tableau 11.4.7 montre un exemple de la manière dont ce calcul peut être effectué systématiquement.

Tableau 11.4.7 . Une table à calculer (gcd(99,53))

Voici un calcul de Sage pour vérifier que (gcd(99, 53) = 1 ext<.>) A ​​chaque ligne, la valeur de (a) est divisée par la valeur de (b ext< .>) Le quotient est placé sur la ligne suivante avec la nouvelle valeur de (a ext<,>) qui est la précédente (b ext<>) et le reste, qui est la nouvelle valeur of (b ext<.>) Rappelez-vous que dans Sage, a%b est le reste lors de la division de b en a .

Enquête 11.4.1 .

Si vous aviez le droit de choisir deux nombres inférieurs à 100, lequel choisiriez-vous pour forcer Euclide à travailler le plus dur ? Voici un indice : la taille du quotient à chaque étape détermine la vitesse à laquelle les nombres diminuent.

Si le quotient de division est 1, alors nous obtenons la complétion la plus lente possible. Si (a = b + r ext<,>) puis en revenant, chaque reste serait la somme des deux restes précédents. Cela décrivait une séquence comme la séquence de Fibonacci et en effet, le plus grand diviseur commun de deux nombres de Fibonacci consécutifs fera le plus de pas pour atteindre une valeur finale de 1.

Pour les valeurs fixes de (a) et (b ext<,>) considérez des entiers de la forme (a x+by) où (x) et (y) peuvent être deux entiers quelconques . Par exemple, si (a) = 36 et (b) = 27, certains de ces résultats sont tabulés ci-dessous avec les valeurs (x) le long de la colonne de gauche et les valeurs (y) en haut.

Remarquez-vous des motifs ? Quelle est la plus petite valeur positive que vous voyez dans ce tableau ? Comment est-il connecté à 36 et 27?

Théorème 11.4.9 .

Si (a) et (b) sont des entiers positifs, la plus petite valeur positive de (ax + by) est le plus grand commun diviseur de (a) et (b ext<,>) (gcd(a,b) exte<.>)

Preuve .

Si (g = gcd(a, b) ext<,>) puisque (g mid a) et (g mid b ext<,>) on sait que (g mid (ax + by)) pour tous les entiers (x) et (y ext<,>) donc (ax + by) ne peut pas être inférieur à (g ext<.>) Pour montrer que (g) est exactement la valeur la moins positive, nous montrons que (g) peut être atteint en étendant l'algorithme d'Euclide. L'exécution de l'algorithme étendu implique la construction d'une table de nombres. La façon dont il est construit maintient un invariant, et par le théorème de la relation invariante, nous pouvons être sûrs que les valeurs souhaitées de (x) et (y) sont produites.

Pour illustrer l'algorithme, le tableau 11.4.10 montre comment calculer (gcd(152,53) ext<.>) Dans la colonne (r), vous trouverez 152 et 53, puis les restes successifs de la division. Ainsi, chaque nombre dans (r) après les deux premiers est le reste après avoir divisé le nombre immédiatement au-dessus dans le nombre suivant. A gauche de chaque reste se trouve le quotient de la division. Dans ce cas, la troisième ligne du tableau nous indique que (152 = 53cdot 2 + 46 ext<.>) La dernière valeur non nulle dans (r) est le plus grand commun diviseur.

Tableau 11.4.10 . L'algorithme euclidien étendu pour calculer (gcd(152,53))

Les colonnes "(s)" et "(t)" sont nouvelles. Les valeurs de (s) et (t) dans chaque ligne sont conservées de sorte que (152s + 53t) soit égal au nombre dans la colonne (r). Remarquerez que

Tableau 11.4.11. Invariant en calcul (gcd(152,53))

(152 = 152cdot 1+ 53cdot 0)
(53 = 152cdot 0 + 53cdot 1)
(46 = 152cdot 1 + 53cdot (-2))
(vdots)
(1 = 152cdot 15 + 53cdot (-43))
(0 = 152 cdot (-53) + 53cdot 152)

L'avant-dernière équation est ce que nous recherchons en fin de compte ! Le problème principal est d'identifier comment déterminer ces valeurs après les deux premières lignes. Les deux premières lignes de ces colonnes seront toujours les mêmes. Regardons le cas général du calcul (gcd(a,b) ext<.>) Si les valeurs (s) et (t) dans les lignes (i - 1) et ( i - 2) sont corrects, nous avons

Si vous remplacez les expressions par (r_) et (r_) de (A) dans cette dernière équation, puis collectez les termes (a) et (b) séparément, vous obtenez

Regardez attentivement les équations pour (r_i, s_i, extrm < et >t_i ext<.>) Leurs formes sont toutes les mêmes. Avec un peu de pratique, vous devriez être capable de calculer rapidement les valeurs (s) et (t).

Sous-section 11.4.3 Arithmétique modulaire

On rappelle la relation sur les entiers que l'on appelle Congruence Modulo (n). Si deux nombres, (a) et (b ext<,>) diffèrent d'un multiple de (n ext<,>) on dit qu'ils sont congrus modulo (n ext<,> ) noté (a equiv bpmod ext<.>) Par exemple, (13 equiv 38pmod<5>) car (13-38 = -25 ext<,>) qui est un multiple de 5.

Définition 11.4.12 . Ajout modulaire.

Si (n) est un entier positif, nous définissons l'addition modulo (n) (left(+_n ight.)) comme suit. Si (a, b in mathbb exte<,>)

Définition 11.4.13 . Multiplication modulaire.

Si (n) est un entier positif, nous définissons la multiplication modulo (n) (left( imes_n ight.)) comme suit. Si (a, b in mathbb exte<,>)

Remarque 11.4.14 .

Le résultat de l'arithmétique modulo (n) est toujours un entier compris entre 0 et (n-1 ext<,>) par la propriété Division. Cette observation implique que (<0, 1,dots, n-1>) est fermé sous l'arithmétique modulo (n).

Il est toujours vrai que (a +_n b equiv (a + b) pmod) et (a imes_n b equiv (a cdot b) pmod ext<.>) Par exemple, (4 +_7 5 = 2 equiv 9 pmod<7>) et (4 imes_7 5 = 6 equiv 20 pmod<7> ext<.> )

Nous utiliserons la notation (mathbb_n) pour désigner l'ensemble (<0, 1, 2,. . ., n-1> ext<.>)

Exemple 11.4.15 . Quelques exemples.

Nous connaissons tous un peu (mathbb_<12>) since the hours of the day are counted using this group, except for the fact that 12 is used in place of 0. Military time uses the mod 24 system and does begin at 0. If someone started a four-hour trip at hour 21, the time at which she would arrive is (21 +_ <24>4 = 1 ext<.>) If a satellite orbits the earth every four hours and starts its first orbit at hour 5, it would end its first orbit at time (5 +_<24>4 =9 ext<.>) Its tenth orbit would end at (5 +_ <24>10 imes_<24>4 =21) hours on the clock

Virtually all computers represent unsigned integers in binary form with a fixed number of digits. A very small computer might reserve seven bits to store the value of an integer. There are only (2^7) different values that can be stored in seven bits. Since the smallest value is 0, represented as 0000000, the maximum value will be (2^7 - 1 = 127 ext<,>) represented as 1111111. When a command is given to add two integer values, and the two values have a sum of 128 or more, overflow occurs. For example, if we try to add 56 and 95, the sum is an eight-digit binary integer 10010111. One common procedure is to retain the seven lowest-ordered digits. The result of adding 56 and 95 would be (0010111_< extrm< two>> = 23 equiv 56 + 95pmod<128> ext<.>) Integer arithmetic with this computer would actually be modulo 128 arithmetic.

Subsection 11.4.4 Properties of Modular Arithmetic

Theorem 11.4.16 . Additive Inverses in (mathbb_n).

If (a in mathbb_n ext<,>) (a eq 0 ext<,>) then the additive inverse of a is (n - a ext<.>)

Preuve .

(a + (n - a) =nequiv 0( extrm < mod >n) ext<,>) since (n = ncdot 1 + 0 ext<.>) Therefore, (a+_n(n-a)=0 ext<.>)

Addition modulo (n) is always commutative and associative 0 is the identity for (+_n) and every element of (mathbb_n) has an additive inverse. These properties can be summarized by noting that for each (ngeq 1 ext<,>) (left[mathbb_n +_n ight]) is a group.

Definition 11.4.17 . The Additive Group of Integers Modulo (n).

The Additive Group of Integers Modulo (n) is the group with domain (<0, 1, 2, dots, n-1>) and with the operation of mod (n) addition. It is denoted as (mathbb_n ext<.>)

Multiplication modulo (n) is always commutative and associative, and 1 is the identity for ( imes_n ext<.>)

Notice that the algebraic properties of (+_n) and ( imes_n) on (mathbb_n) are identical to the properties of addition and multiplication on (mathbb exte<.>)

Notice that a group cannot be formed from the whole set (<0, 1, 2, dots, n-1>) with mod (n) multiplication since zero never has a multiplicative inverse. Depending on the value of (n) there may be other restrictions. The following group will be explored in Exercise 9.

Definition 11.4.18 . The Multiplicative Group of Integers Modulo (n).

The Multiplicative Group of Integers Modulo (n) is the group with domain ( vert 1 leq k leq n-1 extrm< and >gcd(n,k)=1>) and with the operation of mod (n) multiplication. It is denoted as (mathbb_n ext<.>)

Example 11.4.19 . Some operation tables.

Here are examples of operation tables for modular groups. Notice that although 8 is greater than 5, the two groups (mathbb_5) and (mathbb_8) both have order 4. In the case of (mathbb_5 ext<,>) since 5 is prime all of the nonzero elements of (mathbb_5) are included. Since 8 isn't prime we don't include integers that share a common factor with 8, the even integers in this case.

Table 11.4.20 . Operation Table for the group (mathbb_5)

(+_5) (0) (1) (2) (3) (4)
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
Table 11.4.21 . Operation table for the group (mathbb_5)
( imes_5) (1 ) (2) (3) (4)
1 1 2 3 4
2 2 4 1 3
3 3 1 4 2
4 4 3 2 1
Table 11.4.22 . Operation table for the group (mathbb_8)
( imes_8) (1 ) (3) (5) (7)
1 1 3 5 7
3 3 1 7 5
5 5 7 1 3
7 7 5 3 1

Subsection 11.4.5 SageMath Note - Modular Arithmetic

Sage inherits the basic integer division functions from Python that compute a quotient and remainder in integer division. For example, here is how to divide 561 into 2017 and get the quotient and remainder.

In Sage, (gcd) is the greatest common divisor function. It can be used in two ways. For the gcd of 2343 and 4319 we can evaluate the expression (gcd(2343,4319) ext<.>) If we are working with a fixed modulus (m) that has a value established in your Sage session, the expression (m.gcd(k)) to compute the greatest common divisor of (m) and any integer value (k ext<.>) The extended Euclidean algorithm can also be called upon with (xgcd ext<:>)

Sage has some extremely powerful tool for working with groups. The integers modulo (n) are represented by the expression (Integers(n)) and the addition and multiplications tables can be generated as follows.

Once we have assigned (R) a value of (Integers(6) ext<,>) we can do calculations by wrapping (R()) around the integers 0 through 5. Here is a list containing the mod 6 sum and product, respectively, of 5 and 4:

Generating the multiplication table for the family of groups (mathbb_n) takes a bit more code. Here we restrict the allowed inputs to be integers from 2 to 64.

Exercises 11.4.6 Exercises

Determine the greatest common divisors of the following pairs of integers without using any computational assistance.

(2^3 cdot 3^2cdot 5) and (2^2 cdot 3 cdot 5^2cdot 7)

(7! ) and (3cdot 5cdot 7cdot 9cdot 11cdot 13)

(displaystyle 2^2 cdot 3 cdot 5)

(displaystyle 3^2 cdot 5cdot 7)

Find all possible values of the following, assuming that (m) is a positive integer.

(displaystyle 6 imes_8 2 +_8 6 imes_8 5 )

(displaystyle 6 imes_8 left(2 +_85 ight))

(displaystyle 3 imes_5 3 imes_5 3 imes_5 3 equiv 3^4 ( extrm < mod>5))


Class Logistics

Infinite Series C.H. Edwards, Jr. & David E. Penney: Calculus with Analytic Geometry, 5e edition, Prentice Hall, chap. 11.
Notes on Infinite Sequences and Series. Linear Algebra Leonard Evens: Sequences & Series, Linear Algebra (Notes), Northwestern University, Fall 1999. Available at Quartet (on Clark Street, West of Sherman).

The discussion sessions will be held on Thursdays under the supervision of the TAs.

Students whose last name initial is A-K go to Tech LG72 (Parwani).
Students whose last name initial is L-Z go to Lunt 105 (Schemmerhorn).

Homework will be assigned daily but not collected. Several assignments will consists of Maple Worksheets, and these will be collected on the discussion session and graded by the TA.

There will be short quizzes based on the homework from previous lectures on the Thursday discussion sessions.

There will be two one-hour Midterm Exams and one two-hour Final Exam.

  • First Midterm: Thursday, October 14, 1999, 12:00-1:00pm. Infinite Series.
  • Second Midterm: Thursday, November 11, 1999, 12:00-2:00pm. Linear Algebra, chapters I and II.
  • Final: Friday, December 10, 1999, 12:00-2:00pm. It will include questions from the whole syllabus.

Only non graphic non programmable calculators will be allowed in the exams. No make-up exams will be given. In the event of an extreme and well documented absence (such as hospitalization) the final may be weighted to count for the missing exam. In the case of a missed exam, contact the instructor as soon as possible.

The course will be graded as follows:

  • Quiz: 20%
  • Maple Worksheets: 10%
  • Midterms: 40% (20% each)
  • Final: 30%

The lowest quiz score will be dropped in calculating the quizzes grade. There will be no make-up quizzes. If you miss a quiz it will be dropped as your worst quiz grade. The lowest maple worksheet grade will also be dropped.

If you want to change sections, or add/drop the course, please do so at the Math Department Office in Lunt.


Matrix Theory and Linear Algebra in its current form was adapted, thoroughly revised, and extended by Peter Selinger for use at Dalhousie University. It is based on the earlier open text "A first course in linear algebra" by Lyryx Learning, which was in turns an adaptation of the open text "Elementary linear algebra" by Ken Kuttler. Please see inside the book for the full revision history.

Contributors include: Ken Kuttler, Ilijas Farah, Marie-Andrée B. Langlois, Peter Selinger, and the Lyryx Learning Team: Bruce Bauslaugh, Peter Chow, Nathan Friess, Stephanie Keyowski, Claude Laflamme, Martha Laflamme, Jennifer MacKenzie, Tamsyn Murnaghan, Bogdan Sava, Larissa Stone, Ryan Yee, and Ehsun Zahedi. Cover photography by Pok Rie.


Voir la vidéo: PhD Pure Mathematics (Octobre 2021).