We study matrix calculations such as diagonalization of quadratic forms under the aspect of additive complexity and relate these complexities to the complexity of matrix multiplication. While in Bürgisser et al. (1991) for multiplicative complexity the customary thick path existence argument was sufficient, here for additive complexity we need the more delicate finess of the real spectrum (cf. Bochnak et al. (1987), Becker (1986), Knebusch and Scheiderer (1989)) to obtain a complexity relativization....

Soit ${\widetilde{𝒜}}_m$ l’algèbre des fonctions sur ${\mathbf{R}}^n$ engendrée par les fonctions polynomiales et les exponentielles de formes linéaires. La partie $S$ de ${\mathbf{R}}^n$ appartient à ${𝒫}_n$ si et seulement s’il existe $m$ et $F$ dans ${\widetilde{𝒜}}_{n+m}$ pour lesquels $S$ est l’image par la projection canonique de ${\mathbf{R}}^{n+m}$ sur ${\mathbf{R}}^n$, de l’ensemble des zéros de $F$. Soit ${\widetilde{𝒫}}_n$ le plus petit sous-ensemble de parties de ${\mathbf{R}}_n$ qui contient ${𝒫}_n$, l’adhérence de ses éléments et les images par la projection canonique de ${\mathbf{R}}^n$ qui contient ${𝒫}_n$, l’adhérence de ses éléments et les images par la...