Generalizing Cramer's Rule:
Solving uniformly linear systems


with Gema M. Díaz-Toca and Laureano González-Vega
SIAM Journal on Matrix Analysis and Applications 27 3, (2005), 621-637.

Generalizing Cramer's Rule: Solving uniformly linear systems (pdf) dvi file.

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.

Une généralisation de la règle de Cramer:
Résolution uniforme des systèmes linéaires

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.