Résultant d’une matrice polynomiale Henri Lombardi

Notations

On considère une liste Δ = [δ_{1}, …, δ_{r}] avec δ_{1}, …, δ_{r} entiers > 0, fixée pour toute la suite. On appelle “matrice r × s” une matrice à r lignes et s colonnes. On considère la matrice générale r × (r + 1) de polynomes ∈ Z[\underline{c}, X] ; les polynomes de la ligne n^{∘} i étant de degrés ≤ δ_{i}. On note M cette matrice. Ou, en précisant, M(\underline{c}, X). Si K est un anneau commutatif, toute matrice r × (r + 1) à coefficients dans K[X] peut être considérée comme une spécialisée de la matrice générale M.

Pour un polynome P de degré ≤ δ_{i} on notera P_{δ_{i}} le “polynome réciproque de P en degré δ_{i}” défini par: P_{δ_{i}}(X) = X^{δ_{i}} P (1/X). En remplaçant dans la matrice M chaque polynome par son polynome réciproque (le degré étant δ_{i} sur la ligne n^{∘} i) on obtient la “matrice réciproque” que l’on notera ^{∘}M.

On note e_{1}, …, e_{r} la base canonique de K^{r}. On note B_{Δ} la base sur K formée des vecteurs :

X^{δ_{1}}e_{1}, X^{δ_{1}−1}e_{1}, …, Xe_{1}, e_{1}, X^{δ_{2}}e_{2}, …, Xe_{2}, e_{2}, …, Xe_{r}, e_{r}.

Si μ est un entier ≥ 0 on note Δ + μ = [δ_{1} + μ, …, δ_{r} + μ], et donc B_{Δ+μ} est la base sur K formée des vecteurs :

X^{δ_{1}+μ}e_{1}, …, Xe_{1}, e_{1}, X^{δ_{2}+μ}e_{2}, …, e_{2}, …, X^{δ_{r}+μ}e_{r}, …, e_{r}.

On note K[X]_{Δ} et K[X]_{Δ+μ} les espaces vectoriels (modules libres) sur K ayant pour bases B_{Δ} et B_{Δ+μ}.

On note V_{1}, …, V_{r+1} les vecteurs colonnes de la matrice M. On note M^{(μ)} la matrice à coefficients dans Z[\underline{c}] (ou dans K si on a spécialisé) ayant pour vecteurs colonnes les vecteurs

X^{μ}V_{1}, X^{μ}V_{2}, …, X^{μ}V_{r+1}, X^{μ−1}V_{1}, …, X^{μ−1}V_{r+1}, …, XV_{r+1}, V_{1}, …, V_{r+1}

écrits sur la base B_{Δ+μ}. Si K est un corps, notons L(M, μ) le K-espace vectoriel engendré par ces vecteurs. On a: L(M, μ + 1) = L(M, μ) + X.L(M, μ). La matrice M^{(μ)} a (1 + μ)(r + 1) colonnes et (δ_{1} + … + δ_{r}) + (1 + μ)r lignes. Posons δ = δ_{1} + ⋯ + δ_{r} − 1. On voit que M^{(δ)} est une matrice carrée.

Définition : Le déterminant de M^{(δ)} est appelé le résultant de la matrice M.

N.B. : Au signe près M et ^{∘}M ont même résultant.

Homogénéisation : On note M^{h} la matrice homogénéisée de M. (chaque polynome de ligne n^{∘} i est homogénéisé au degré δ_{i}) On note B_{Δ}^{h} l’homogénéisée de la base B_{Δ} :

X^{δ_{1}}e_{1}, X^{δ_{1}−1}Y e_{1}, …, Y^{δ_{1}}e_{1}, …, X^{δ_{r}}e_{r}, …, Y^{δ_{r}}e_{r}

La base B_{Δ}^{h} est la base d’un K−espace vectoriel K[X, Y]_{Δ}^{h} contenu dans K[X, Y]. Si on regarde la matrice M^{h} comme la matrice d’une application K[X, Y]-linéaire du module K[X, Y]^{r+1} (avec pour base f_{1}, …, f_{r+1}) vers le module K[X, Y]^{r} (avec pour base e_{1}, …, e_{r}), on voit que l’image du K-espace vectoriel (K[X, Y]_{[μ]}^{h})^{r+1} (engendré par les X^{α}Y^{μ−α}f_{j} est contenue dans K[X, Y]_{Δ+μ}^{h}, et que la matrice de l’application K-linéaire ainsi définie (par rapport aux bases convenables) est précisément la matrice M^{(μ)}.

Réductions de matrices

Triangulation sans échange de ligne : Étant donnée une matrice A à coefficients dans un corps K, nous appelons triangulation sans échange de ligne de A, le processus qui ramène, par manipulations élémentaires de colonnes (échange de deux colonnes, ou remplacement d’une colonne C_{i} par C_{i} + a.C_{j} avec i ≠ j), la matrice A à une forme échelonnée en colonnes (i. e. les colonnes successives ont leur premier coefficient non nul de plus en plus bas jusqu’à ce que, éventuellement les colonnes restantes soient toutes nulles). On appellera pivots les entrées de la matrice réduite qui sont les premiers coefficients non nuls dans les colonnes successives. La position des pivots (ou encore la liste des numéros de lignes des pivots) ne dépend que de la matrice de départ. La matrice A a son rang égal à son nombre de lignes (i.e. elle définit une application linéaire surjective), si et seulement si cette réduction produit une matrice sous-triangulaire avec des éléments non nuls sur la diagonale principale.

Réduction de Hermite d’une matrice de polynomes : Il s’agit d’une généralisation de la triangulation précédente, pour le cas où les entrées sont dans un anneau de Bezout. Nous traitons le cas particulier qui nous intéresse. Étant donnée une matrice r × s A à coefficients dans un anneau K[X] (où K est un corps), nous appelons réduction de Hermite de la matrice A la donnée d’une matrice r × s échelonnée en colonnes B et d’une matrice s×s unimodulaire (ayant pour déterminant une constante non nulle) P telles que A.P = B. La matrice B est appelée une réduite de Hermite de A. On appellera pivots les entrées de la réduite de Hermite qui sont les premiers coefficients non nuls dans les colonnes successives. La position et la valeur des pivots (à un facteur scalaire non nul près) ne dépendent que de la matrice de départ A. Au regard de cette unicité, nous parlerons désormais de “la” rèduite de Hermite de la matrice A. Le produit des k premiers pivots de la réduite de Hermite est égal au pgcd des mineurs k × k extraits sur les lignes des k premiers pivots.

Une matrice r×s A définit une application surjective (i.e. ses vecteurs colonnes engendrent le K[X]-module K[X]^{r}) si et seulement si la réduite de Hermite admet un pivot inversible (i.e. égal à une constante non nulle) sur chaque lignece qui revient à dire que le pgcd des r-mineurs de A est une constante non nulle.

Un exemple pour voir Avec Δ = [4, 2], on a δ = 5. Si la matrice spécialisée M est donnée par

( \begin{matrix}X^{4} + 2X + 3 & X^{3} + X^{2} + 1 & X^{4} + X^{2} \\ X^{2} + X + 7 & 3X^{2} + 1 & X + 2 \end{matrix} )

alors la matrice ^{∘}M est égale à

( \begin{matrix}3X^{4} + 2X^{3} + 1 & X^{4} + X^{2} + X & X^{2} + 1 \\ 7X^{2} + X + 1 & X^{2} + 3 & 2X^{2} + X \end{matrix} )

la matrice M^{h} est égale à

( \begin{matrix}3Y^{4} + 2Y^{3}X + X^{4} & Y^{4} + Y^{2}X^{2} + Y X^{3} & Y^{2}X^{2} + X^{4} \\ 7Y^{2} + Y X + X^{2} & Y^{2} + 3X^{2} & 2Y^{2} + Y X \end{matrix} )

et la matrice M^{(δ)} est égale à

\begin{matrix}| & 1 & 0 & 1 & | & . & . & . & | & . & . & . & | & . & . & . & | & . & . & . & | & . & . & . & | \\ | & 0 & 1 & 0 & | & 1 & 0 & 1 & | & . & . & . & | & . & . & . & | & . & . & . & | & . & . & . & | \\ | & 0 & 1 & 1 & | & 0 & 1 & 0 & | & 1 & 0 & 1 & | & . & . & . & | & . & . & . & | & . & . & . & | \\ | & 2 & 0 & 0 & | & 0 & 1 & 1 & | & 0 & 1 & 0 & | & 1 & 0 & 1 & | & . & . & . & | & . & . & . & | \\ | & 3 & 1 & 0 & | & 2 & 0 & 0 & | & 0 & 1 & 1 & | & 0 & 1 & 0 & | & 1 & 0 & 1 & | & . & . & . & | \\ | & . & . & . & | & 3 & 1 & 0 & | & 2 & 0 & 0 & | & 0 & 1 & 1 & | & 0 & 1 & 0 & | & 1 & 0 & 1 & | \\ | & . & . & . & | & . & . & . & | & 3 & 1 & 0 & | & 2 & 0 & 0 & | & 0 & 1 & 1 & | & 0 & 1 & 0 & | \\ | & . & . & . & | & . & . & . & | & . & . & . & | & 3 & 1 & 0 & | & 2 & 0 & 0 & | & 0 & 1 & 1 & | \\ | & . & . & . & | & . & . & . & | & . & . & . & | & . & . & . & | & 3 & 1 & 0 & | & 2 & 0 & 0 & | \\ | & . & . & . & | & . & . & . & | & . & . & . & | & . & . & . & | & . & . & . & | & 3 & 1 & 0 & | \\ | & 1 & 3 & 0 & | & . & . & . & | & . & . & . & | & . & . & . & | & . & . & . & | & . & . & . & | \\ | & 1 & 0 & 1 & | & 1 & 3 & 0 & | & . & . & . & | & . & . & . & | & . & . & . & | & . & . & . & | \\ | & 7 & 1 & 2 & | & 1 & 0 & 1 & | & 1 & 3 & 0 & | & . & . & . & | & . & . & . & | & . & . & . & | \\ | & . & . & . & | & 7 & 1 & 2 & | & 1 & 0 & 1 & | & 1 & 3 & 0 & | & . & . & . & | & . & . & . & | \\ | & . & . & . & | & . & . & . & | & 7 & 1 & 2 & | & 1 & 0 & 1 & | & 1 & 3 & 0 & | & . & . & . & | \\ | & . & . & . & | & . & . & . & | & . & . & . & | & 7 & 1 & 2 & | & 1 & 0 & 1 & | & 1 & 3 & 0 & | \\ | & . & . & . & | & . & . & . & | & . & . & . & | & . & . & . & | & 7 & 1 & 2 & | & 1 & 0 & 1 & | \\ | & . & . & . & | & . & . & . & | & . & . & . & | & . & . & . & | & . & . & . & | & 7 & 1 & 2 & | \end{matrix}

où les points “.” représentent des zéros “structurels”. Le résultant de M est égal à −427122.

Le théorème principal

Théorème 1 Soit une liste Δ = [δ_{1}, …, δ_{r}] avec δ_{1}, …, δ_{r} entiers > 0, soit M(X) la matrice générale associée à Δ définie au début de k’article, et soit ρ son résultant. On spécialise les coefficients dans un corps K. On considère une extension algébriquement close L de K. Les conditions suivantes sont équivalentes (1a) ρ ≠ 0 (i.e. M^{(δ)} est régulière) (1b) la matrice M^{h}(X, Y) définit une application surjective de (K[X, Y]_{[δ]}^{h})^{r+1} vers

K[X, Y]_{Δ+δ}^{h}

(1c) la triangulation sans échange de lignes de la matrice M^{(δ)} fournit un pivot sur chaque

ligne. (2a) M(X) et ^{∘}M(X) définissent des applications surjectives de K[X]^{r+1} vers K[X]^{r} (2b) la réduite de Hermite de M(X) admet sur chaque ligne un pivot égal à une constante

non nulle, et la même chose pour ^{∘}M(X) (2c) le pgcd des r−mineurs de M(X) est une constante ≠ 0, et la même chose pour ^{∘}M(X)

(3) pour tous x, y dans L (avec (x, y) ≠ (0, 0)) la matrice M^{h}(x, y) définit une application surjective de L^{r+1} vers L^{r} (i.e. : un r−mineur de la matrice au moins est non nul)

(4) pour μ assez grand, la matrice M^{h}(X, Y) définit une application surjective de (K[X, Y]_{[μ]}^{h})^{r+1} vers K[X, Y]_{Δ+μ}^{h}

(5) comme (4) mais avec μ ≥ δ

(6) la triangulation sans échange de lignes de la matrice M^{(δ)} fournit des pivots sur les lignes e_{i} et sur les lignes e_{i}X^{δ_{i}+δ}

preuve On note que pour r = 1, le théorème est bien connu. Traitons le cas général. On a clairement (1a) ⇔ (1b) ⇔ (1c). On notera indifféremment (1) une de ces propriétés. Notons (2a.1) la partie de (2a) qui concerne M, et (2a.2) celle qui concerne ^{∘}M. Faisons de même pour (2b) (qui signifie (2b.1) et (2b.2)) et pour (2c) (qui signifie (2c.1) et (2c.2)). Les équivalences (2a.1) ⇔ (2b.1) ⇔ (2c.1) sont claires d’après la théorie des réduites de Hermite. On notera indifféremment (2.1) une de ces propriétés. On a de même (2a.2) ⇔ (2b.2) ⇔ (2c.2) (qu’on notera (2.2)), et donc (2a) ⇔ (2b) ⇔ (2c) (qu’on notera (2)). Notons (3.1) pour : pour tout x ∈ L la matrice M^{h}(x, 1) définit une application surjective de L^{r+1} vers L^{r}. Notons (3.2) pour : pour tout y ∈ L la matrice M^{h}(1, y) définit une application surjective de L^{r+1} vers L^{r}. Il est clair que (3) ⇔ (3.1) et (3.2)

Les seuls polynomes partout non nuls (dans L) étant les constantes non nulles, on a l’équivalence de :

(i) le pgcd des r−mineurs de M(X) est une constante ≠ 0

(ii) ∀ x ∈ L la matrice M(x) a un de ses mineurs non nuls

(iii) ∀ x ∈ L, la matrice M(x) est la matrice d’une application surjective de L^{r+1} vers L^{r}.

On a donc (2c.1) ⇔ (3.1). De la même manière (2c.2) ⇔ (3.2). Donc (2) ⇔ (3) On a évidemment (5) ⇒ (4), puisqu’on affirme la même chose de manière un peu plus précise en (5) On note que M^{h}(X, 1) = M(X) et M^{h}(1, Y) =^{∘} M(Y). Par ailleurs, après remplacement de Y par 1, K[X, Y]_{[μ]}^{h} devient K[X]_{[μ]} et K[X, Y]_{Δ+μ}^{h} devient K[X]_{Δ+μ}, donc (4) ⇒ (2a). Notons que (1) signifie que L(M, δ) (le K-espace vectoriel engendré par les vecteurs colonnes de M^{(δ)}) est égal à K[X]_{Δ+δ}. La propriété L(M, μ) = K[X]_{Δ+μ} passe de μ à μ+1 parce que L(M, μ+1) = L(M, μ)+X.L(M, μ), et K[X]_{Δ+(μ+1)} = K[X]_{Δ+μ}+X.K[X]_{Δ+μ}. Donc (1) ⇒ (5).

Ceci fournit (1) ⇒ (5) ⇒ (4) ⇒ (2) et (2) ⇔ (3). Il nous reste à montrer (2) ⇒ (6) ⇒ (1). La preuve sera basée sur l’analyse du processus de triangulation des matrices M^{(μ)}. Cette analyse détaillée est esentiellement celle de l’article [LLM92]. Notons (6.1) pour : la triangulation sans échange de lignes de la matrice M^{(δ)} fournit un pivot sur chaque ligne e_{i}. Notons (6.2) pour : la triangulation sans échange de lignes de la matrice M^{(δ)} fournit un pivot sur chaque ligne e_{i}X^{δ_{i}+δ}. On a (6.1) ⇒ (2b.1) (le K[X]-module engendré par les vecteurs colonnes contient des vecteurs convenables (i.e. avec pour première composante non nulle un inversible, pour chaque numéro de ligne). Aussi bien (2c.1) que (2c.2) impliquent que les vecteurs V_{1}, …, V_{r+1} engendrent K(X)^{r} comme K(X) espace vectoriel. On peut donc supposer sans perte de généralité que V_{1}, …, V_{r} sont K[X]−indépendants, i.e. le premier mineur de M est non nul. L’implication (2.1) ⇒ (6.1) sera assurée si on sait que la triangulation de M^{(δ)} fournit (les vecteurs colonnes d’) une réduite de Hermite de M. La même preuve que celle de la proposition 4 de l’article [LLM92] donne le résultat un peu plus faible suivant :

lemme 1 : Supposons que V_{1}, …, V_{r} sont K[X]−indépendants. Soit N = \frac{M}{0,...,01} (N est non singulière). La triangulation de N^{(δ+1)} fournit la réduite de Hermite de N.

Dans la matrice M^{(δ)} on peut rejeter toutes les colonnes X^{α} V_{r+1} à la fin. Quand on triangule cette matrice M^{(δ)}, avant d’atteindre les X^{α} V_{r+1} on a seulement manipulé des X^{k} V_{i} avec i ≤ r, et en conséquence, aucun vecteur ne peut être tué (cela fournirait une K[X]−dépendance linéaire entre V_{1}, …, V_{r}). Pendant ce début de triangulation, les pivots sont au nombre de r(1+δ) cad r(δ_{1}+⋯+δ_{r}). Seules (1 + δ) lignes sont non atteintes. Or chaque zone occupe au moins 2 + δ lignes (δ_{i} + δ + 1 avec δ_{i} > 0). Donc la triangulation de M^{(δ)} “atteint” toutes les zones. Et celle de N^{(δ)} atteint, ou bien les r premières zones, ou bien toutes les zones (cad (r + 1)). Si la triangulation de N^{(δ)} atteint les r premières zones (mais pas la dernière), les (r + 1) nouvelles colonnes, dans la triangulation de N^{(δ+1)}, doivent fournir:

- d’une part des pivots dans chacune des zones 1, …, r de même degré que pour N^{(δ)} - d’autre part un pivot dans la zone r + 1 donc, les r + 1 nouveaux vecteurs ne produisent aucun abaissement de degré de pivots. Si la triangulation de N^{(δ)} atteint toutes les zones, alors par le même argument, celle de N^{(δ+1)} ne fournit pas des pivots de la réduite de Hermite de N de plus bas degrés. En fait cette analyse a établi précisément le fait suivant : lemme 2 : (rappel : les δ_{i} sont > 0). Si un r−mineur de M est non nul, la triangulation de M^{(δ)} fournit la réduite de Hermite de M. Ceci montre donc l’implication (2c.1) ⇒ (6.1). L’implication (2c.2) ⇒ (6.2) s’en déduit en considérant la matrice réciproque. Donc (2) ⇒ (6). Voyons maintenant ((6.1) et (6.2)) ⇒ (1c) (i.e. (6) ⇒ (1)). Comme (6.1) ⇒ (2.1), on peut appliquer le lemme 2. Supposons non (1c), (6.1) et (6.2). Cela signifierait qu’il y aurait un trou entre les lignes e_{i} et e_{i} X^{δ_{i}+δ}, pour au moins un i, en ce qui concerne les pivots de la triangulée de M^{(δ)}. Dans le passage de M^{(δ)} à M^{(δ+1)} la nouvelle triangulation absorbe donc 2 des (r + 1) vecteurs pour des pivots dans la zone i

- un tout en bas (pour reproduire le plus bas degré)

- un au niveau du trou (pour reproduire le degré minimum juste au-dessus du trou). Or ceci est contradictoire avec l’analyse qui a conduit au lemme 2 car elle a montré que dans N^{(δ+1)}, les r + 1 dernières colonnes sont absorbées chacune pour une des zones de N^{(δ+1)}. On a donc bien (6) ⇒ (1c).

♢

[LLM96] Labhalla S.,Lombardi H., Marlin R. Algorithmes de calcul de la réduction de Hermite d’une matrice a coefficients polynomiaux. Theoretical Computer Science 161 (1996), 69–92

Futur ?

Corollaire 1 : en gros, comme le théorème, mais avec K un anneau commutatif. (1a) formulé avec ρ inversible et (1b) restent équivalents. (1c) disparait. (2b) disparait. (2c) doit être reformulé en utilisant l’idéal engendré, (il doit contenir 1), et non le pgcd. (3) doit être reformulé avec “pour n’importe quel homomorphisme de K dans un corps”, et la preuve dépend de l’axiome de l’idéal premier. (6) disparait. Il y a peut tre aussi des énoncés avec l’injectivité et les non diviseurs de zéros remplaçant la surjectivité et les inversibles