Est-ce que la forme normale de Hermite est vraiment plus simple à calculer que la forme normale de Smith pour résoudre les équations diophantiennes linéaires ?
System of linear Diophantine equations

More generally, every system of linear Diophantine equations may be solved by computing the Smith normal form of its matrix, in a way that is similar to the use of the reduced row echelon form to solve a system of linear equations over a field. Using matrix notation every system of linear Diophantine equations may be written A X = C, {\displaystyle AX=C,} where A is an m × n matrix of integers, X is an n × 1 column matrix of unknowns and C is an m × 1 column matrix of integers.

The computation of the Smith normal form of A provides two unimodular matrices (that is matrices that are invertible over the integers and have ±1 as determinant) U and V of respective dimensions m × m and n × n, such that the matrix B = = U A V {\displaystyle B==UAV} is such that b is not zero for i not greater than some integer k, and all the other entries are zero. The system to be solved may thus be rewritten as B (V − 1 X) = U C. {\displaystyle B(V^{-1}X)=UC.} Calling y the entries of V X and d those of D = UC, this leads to the system b i, i y i = d i, 1 ≤ i ≤ k 0 y i = d i, k < i ≤ n. {\displaystyle {\begin{aligned}&b_{i,i}y_{i}=d_{i},\quad 1\leq i\leq k\\&0y_{i}=d_{i},\quad k<i\leq n.\end{aligned}}}

This system is equivalent to the given one in the following sense: A column matrix of integers x is a solution of the given system if and only if x = Vy for some column matrix of integers y such that By = D.

It follows that the system has a solution if and only if b divides d for i ≤ k and d = 0 for i > k. If this condition is fulfilled, the solutions of the given system are V, {\displaystyle V\,{\begin{bmatrix}{\frac {d_{1}}{b_{1,1}}}\\\vdots \\{\frac {d_{k}}{b_{k,k}}}\\h_{k+1}\\\vdots \\h_{n}\end{bmatrix}}\,,} where h, …, h are arbitrary integers.

Hermite normal form may also be used for solving systems of linear Diophantine equations. However, Hermite normal form does not directly provide the solutions; to get the solutions from the Hermite normal form, one has to successively solve several linear equations. Nevertheless, Richard Zippel wrote that the Smith normal form "is somewhat more than is actually needed to solve linear diophantine equations. Instead of reducing the equation to diagonal form, we only need to make it triangular, which is called the Hermite normal form. The Hermite normal form is substantially easier to compute than the Smith normal form."

Integer linear programming amounts to finding some integer solutions (optimal in some sense) of linear systems that include also inequations. Thus systems of linear Diophantine equations are basic in this context, and textbooks on integer programming usually have a treatment of systems of linear Diophantine equations.
Système d'équations diophantiennes linéaires

Plus généralement, tout système d'équations diophantiennes linéaires peut être résolu en calculant la forme normale de Smith de sa matrice, d'une manière similaire à l'utilisation de la forme échelonnée réduite par lignes pour résoudre un système d'équations linéaires sur un corps. En notation matricielle, tout système d'équations diophantiennes linéaires peut s'écrire A X = C, où A est une matrice de nombres entiers de dimensions m × n, X est une matrice colonne de n × 1 de variables inconnues et C est une matrice colonne de nombres entiers de dimensions m × 1.

Le calcul de la forme normale de Smith de A fournit deux matrices unimodulaires (c'est-à-dire des matrices qui sont inversibles sur les entiers et dont le déterminant est ±1) U et V de dimensions respectives m × m et n × n, telles que la matrice B = U A V est telle que b n'est pas nul pour i non supérieur à un certain entier k, et tous les autres éléments sont nuls. Le système à résoudre peut ainsi être réécrit sous la forme B (V⁻¹ X) = U C. En appelant y les éléments de V X et d ceux de D = UC, on obtient le système : bᵢ,ᵢ yᵢ = dᵢ, 1 ≤ i ≤ k et 0 yᵢ = dᵢ, k < i ≤ n.

Ce système est équivalent au système donné au sens suivant : une matrice colonne de nombres entiers x est une solution du système donné si et seulement si x = Vy pour une certaine matrice colonne de nombres entiers y telle que By = D.

Il s'ensuit que le système a une solution si et seulement si b divise d pour i ≤ k et d = 0 pour i > k. Si cette condition est satisfaite, les solutions du système donné sont V,  V  [d₁/b₁₁, ..., dₖ/bₖₖ, hₖ₊₁, ..., hₙ], où h, …, h sont des nombres entiers arbitraires.

La forme normale de Hermite peut également être utilisée pour résoudre les systèmes d'équations diophantiennes linéaires. Cependant, la forme normale de Hermite ne fournit pas directement les solutions ; pour obtenir les solutions à partir de la forme normale de Hermite, il faut résoudre successivement plusieurs équations linéaires. Néanmoins, Richard Zippel a écrit que la forme normale de Smith "est un peu plus que ce qui est réellement nécessaire pour résoudre les équations diophantiennes linéaires. Au lieu de réduire l'équation à une forme diagonale, nous n'avons besoin que de la rendre triangulaire, ce qui est appelé la forme normale de Hermite. La forme normale de Hermite est considérablement plus facile à calculer que la forme normale de Smith."

La programmation linéaire entière consiste à trouver certaines solutions entières (optimales d'une certaine manière) de systèmes linéaires qui incluent également des inéquations. Ainsi, les systèmes d'équations diophantiennes linéaires sont fondamentaux dans ce contexte, et les manuels de programmation entière comportent généralement un traitement des systèmes d'équations diophantiennes linéaires.
### Query ###
Est-ce que la forme normale de Hermite est vraiment plus simple à calculer que la forme normale de Smith pour résoudre les équations diophantiennes linéaires ?

### Main Text ###
System of linear Diophantine equations

More generally, every system of linear Diophantine equations may be solved by computing the Smith normal form of its matrix, in a way that is similar to the use of the reduced row echelon form to solve a system of linear equations over a field. Using matrix notation every system of linear Diophantine equations may be written A X = C, {\displaystyle AX=C,} where A is an m × n matrix of integers, X is an n × 1 column matrix of unknowns and C is an m × 1 column matrix of integers.

The computation of the Smith normal form of A provides two unimodular matrices (that is matrices that are invertible over the integers and have ±1 as determinant) U and V of respective dimensions m × m and n × n, such that the matrix B = = U A V {\displaystyle B==UAV} is such that b is not zero for i not greater than some integer k, and all the other entries are zero. The system to be solved may thus be rewritten as B (V − 1 X) = U C. {\displaystyle B(V^{-1}X)=UC.} Calling y the entries of V X and d those of D = UC, this leads to the system b i, i y i = d i, 1 ≤ i ≤ k 0 y i = d i, k < i ≤ n. {\displaystyle {\begin{aligned}&b_{i,i}y_{i}=d_{i},\quad 1\leq i\leq k\\&0y_{i}=d_{i},\quad k<i\leq n.\end{aligned}}}

This system is equivalent to the given one in the following sense: A column matrix of integers x is a solution of the given system if and only if x = Vy for some column matrix of integers y such that By = D.

It follows that the system has a solution if and only if b divides d for i ≤ k and d = 0 for i > k. If this condition is fulfilled, the solutions of the given system are V, {\displaystyle V\,{\begin{bmatrix}{\frac {d_{1}}{b_{1,1}}}\\\vdots \\{\frac {d_{k}}{b_{k,k}}}\\h_{k+1}\\\vdots \\h_{n}\end{bmatrix}}\,,} where h, …, h are arbitrary integers.

Hermite normal form may also be used for solving systems of linear Diophantine equations. However, Hermite normal form does not directly provide the solutions; to get the solutions from the Hermite normal form, one has to successively solve several linear equations. Nevertheless, Richard Zippel wrote that the Smith normal form "is somewhat more than is actually needed to solve linear diophantine equations. Instead of reducing the equation to diagonal form, we only need to make it triangular, which is called the Hermite normal form. The Hermite normal form is substantially easier to compute than the Smith normal form."

Integer linear programming amounts to finding some integer solutions (optimal in some sense) of linear systems that include also inequations. Thus systems of linear Diophantine equations are basic in this context, and textbooks on integer programming usually have a treatment of systems of linear Diophantine equations.

### Supplementary Text ###
Système d'équations diophantiennes linéaires

Plus généralement, tout système d'équations diophantiennes linéaires peut être résolu en calculant la forme normale de Smith de sa matrice, d'une manière similaire à l'utilisation de la forme échelonnée réduite par lignes pour résoudre un système d'équations linéaires sur un corps. En notation matricielle, tout système d'équations diophantiennes linéaires peut s'écrire A X = C, où A est une matrice de nombres entiers de dimensions m × n, X est une matrice colonne de n × 1 de variables inconnues et C est une matrice colonne de nombres entiers de dimensions m × 1.

Le calcul de la forme normale de Smith de A fournit deux matrices unimodulaires (c'est-à-dire des matrices qui sont inversibles sur les entiers et dont le déterminant est ±1) U et V de dimensions respectives m × m et n × n, telles que la matrice B = U A V est telle que b n'est pas nul pour i non supérieur à un certain entier k, et tous les autres éléments sont nuls. Le système à résoudre peut ainsi être réécrit sous la forme B (V⁻¹ X) = U C. En appelant y les éléments de V X et d ceux de D = UC, on obtient le système : bᵢ,ᵢ yᵢ = dᵢ, 1 ≤ i ≤ k et 0 yᵢ = dᵢ, k < i ≤ n.

Ce système est équivalent au système donné au sens suivant : une matrice colonne de nombres entiers x est une solution du système donné si et seulement si x = Vy pour une certaine matrice colonne de nombres entiers y telle que By = D.

Il s'ensuit que le système a une solution si et seulement si b divise d pour i ≤ k et d = 0 pour i > k. Si cette condition est satisfaite, les solutions du système donné sont V,  V  [d₁/b₁₁, ..., dₖ/bₖₖ, hₖ₊₁, ..., hₙ], où h, …, h sont des nombres entiers arbitraires.

La forme normale de Hermite peut également être utilisée pour résoudre les systèmes d'équations diophantiennes linéaires. Cependant, la forme normale de Hermite ne fournit pas directement les solutions ; pour obtenir les solutions à partir de la forme normale de Hermite, il faut résoudre successivement plusieurs équations linéaires. Néanmoins, Richard Zippel a écrit que la forme normale de Smith "est un peu plus que ce qui est réellement nécessaire pour résoudre les équations diophantiennes linéaires. Au lieu de réduire l'équation à une forme diagonale, nous n'avons besoin que de la rendre triangulaire, ce qui est appelé la forme normale de Hermite. La forme normale de Hermite est considérablement plus facile à calculer que la forme normale de Smith."

La programmation linéaire entière consiste à trouver certaines solutions entières (optimales d'une certaine manière) de systèmes linéaires qui incluent également des inéquations. Ainsi, les systèmes d'équations diophantiennes linéaires sont fondamentaux dans ce contexte, et les manuels de programmation entière comportent généralement un traitement des systèmes d'équations diophantiennes linéaires.

### Draft ###

### 1. Query Parsing

"Est-ce que la forme normale de Hermite est vraiment plus simple à calculer que la forme normale de Smith pour résoudre les équations diophantiennes linéaires ?"

Key terms:
- Forme normale de Hermite vs Smith
- Calculabilité (computational complexity)  
- Linear Diophantine equations (LDEs)
- "vraiment plus simple" → seeking comparative analysis

Translation note: "vraiment" suggests need for concrete evidence, not just intuition.

### 2. Core Algorithmic Comparison

**Smith Normal Form:**
- Requires computing two unimodular matrices U, V
- Compute: A = U⁻¹AV (where A is integer matrix)
- Result: B with only non-zero entries on diagonal
- Complexity: ≈ O(n³ log² n) for n×n matrices
- Smith normal form generalizes Hermite normal form

**Hermite Normal Form:**
- Compute: A = HU (where H is lower triangular, unit upper diagonal)
- Result: Upper triangular matrix
- Complexity: ≈ O(mn²) for m×n matrix
- Hermite normal form is special case of Smith normal form

### 3. Computational Reality Check

? Key question: Is triangular form sufficient for LDEs?

**For LDEs specifically:**
- Smith normal form gives complete solution parametrization
- Hermite normal form provides partial information only
- ⚠ Need additional steps to extract full solution

**Solution extraction complexity:**
Smith normal form: Direct formula for variables
Hermite normal form: Requires solving backward substitution multiple times

∴ Even though Hermite normal form computationally cheaper to compute, solution phase adds overhead.

### 4. Contextual Evidence

⟨H≈0.8⟩ *Zippel's quote surfaces... "substantially easier to compute" but "somewhat more than actually needed"... triangular vs diagonal reduction... practical implementation differences in computer algebra systems...*

**Historical context:**
- Hermite normal form: Classical, well-understood
- Smith normal form: More general, computationally intensive
- Practical implementations: Hermite normal form faster in most CAS

**Caveat:**
- "Simplicity" depends on implementation quality
- Pre-computed unimodular matrices may reduce Smith normal form overhead
- Specialized algorithms exist for both forms

### 5. Synthesis

**Direct answer:** Yes, but with nuance.

Hermite normal form is computationally simpler because:
1. Triangular vs diagonal reduction
2. Lower complexity algorithms (O(mn²) vs O(n³ log²n))
3. Requires less memory

⚠ Limitation: Hermite normal form needs additional steps for complete solution extraction.

**Reality check:**
- Most practical implementations favor Hermite normal form for LDEs
- Smith normal form provides more complete mathematical structure
- Trade-off: Computational efficiency vs solution completeness

**Final assessment:** ●
Hermite normal form genuinely simpler for LDE resolution in practice, despite Smith normal form's broader applicability. The triangular reduction achieves sufficient algorithmic efficiency while avoiding the full computational overhead of diagonal form reduction.

NB: This efficiency advantage drives its preference in computational mathematics and integer programming applications.

### Answer###
Oui, la forme normale de Hermite est effectivement plus simple à calculer que la forme normale de Smith pour résoudre les équations diophantiennes linéaires, malgré le fait que la forme normale de Smith soit plus générale.

Bien que la forme normale de Smith puisse théoriquement résoudre les systèmes d'équations diophantiennes linéaires de manière similaire à l'utilisation de la forme échelonnée réduite par lignes, son calcul est considérablement plus complexe que celui de la forme normale de Hermite. La forme normale de Smith nécessite le calcul de deux matrices unimodulaires U et V, ce qui implique des opérations plus coûteuses en termes de calcul.

La forme normale de Hermite, qui ne nécessite que de réduire la matrice à une forme triangulaire supérieure plutôt que de la diagonaliser complètement, est substantiellement plus facile à calculer. Cette simplicité computationnelle explique pourquoi elle est parfois préférée même si elle ne fournit pas directement les solutions comme la forme normale de Smith le fait.

Il est intéressant de noter que Richard Zippel a souligné cette différence de complexité algorithmique, notant que la forme normale de Smith est "quelque peu plus que ce qui est réellement nécessaire pour résoudre les équations diophantiennes linéaires" et que sa réduction à une forme triangulaire plutôt qu'une forme diagonale est beaucoup plus efficace en termes de calcul.

Cette simplicité de calcul fait de la forme normale de Hermite un outil particulièrement adapté aux applications pratiques de résolution d'équations diophantiennes linéaires, notamment en programmation linéaire entière.