Abstract : We explain how the computation of a characteristic polynomial allows to determine the rank of a matrix and to solve uniformly (with a unique formula, of Cramer style) linear systems over an arbitray field. This constitutes an extension of a result of Mulmuley, who dealed only with the rank of the matrix. Applications of our method are to be found in parallel computations and in solving linear system depending on parameters.
Résumé :
Nous expliquons ici comment un calcul de polynôme caractéristique permet de déterminer le
rang d'une matrice et de résoudre uniformément (avec
une seule formule, du type Cramer) les systèmes d'équations linéaires ayant un format
donné et un rang fixé. Et ceci sur un corps arbitraire.
Ceci constitue une extension d'un résultat de Mulmuley
qui ne traite que la question du rang.
Naturellement, le rang d'une matrice peut être calculé par
la méthode du pivot de Gauss. Mais la méthode n'est pas
uniforme et, a priori, ne se laisse pas bien paralléliser.
Les applications des formules et algorithmes que nous décrivons
ici seront de deux ordres: d'une part en calcul parallèle, d'autre
part lorsqu'on doit traiter des systèmes d'équations linéaires dépendant de paramètres.