. ?-j-?-m} and . Then, PE is a ?s-weak Popov basis of K(F)

, We first prove that the number of rows of PE is the rank of K(F), that is, k = m ? rank(F)

.. , m} \ {? 1 + · · · + ? j , 1 ? j ? m} sorted in increasing order. Since P is the submatrix of the rows of Q whose ?s-pivot index is not in this set, P has k = r ? (m ? m) = m ? rank(F) rows. Now, by construction, P is in ?s-weak Popov form and its ?s-pivot index has entries in {? 1 + · · · + ? i , 1 ? i ? m}. Thus we can apply Lemma 5.7; it ensures that PE is in ?s-weak Popov form and that rdeg ?s (PE) = rdeg ?s (P). It remains to prove that PE is a basis of K(F), Item (iv) of Lemma 5.9, the ?s-pivot index of the ?s-Popov basis of K(EF) contains the ?s-pivot index of S. By Lemma 5.8, the latter is the tuple formed by the integers in the set {1

. Then, Since P (resp. K) is the submatrix of the rows of Q (resp. B) whose ?s-pivot index is in {? 1 + · · · + ? j , 1 ? j ? m}, and since both P and K are in ?s-weak Popov form, it follows that P and K have the same ?s-pivot profile. In particular, we have rdeg ?s (P) = rdeg ?s (K) = d, from which we get rdeg ?s (PE) = d. According to Lemma 2.3, since the rows of PE are in K(F), this implies that PE is a basis of K(F). 6: Apply Definition 5.12 to (?, EF, ? + 1) to obtain the order L ?+1 (?) ? Z n+n >0 and the matrix L ?

?. and .. , ?) ? Z m+n ?0

?. Max,

(. G-=-l-?,?+1, .. .. Ef)x-(?, and .. ;-?, ?)?L ?+1 (?) use uniform order

M. and G. , Step 4: Deduce first ?s-weak Popov basis of K(EF), then ?s-weak, m+n)×(m+n) ? PM-Basis, vol.11

. Q-?-k, P ? K[x] k×m ? the rows of Q whose ?s-pivot index is in {? 1 + · · · + ? j , 1 ? j ? m} 14: return PE Proposition 5.14. Algorithm 4 is correct. Let D = max(|s|, |cdeg s (F)|, 1). Then, assuming m ? n and using notation from the algorithm, its cost is bounded by the sum of: ? the cost of performing PM-Basis at order at most 2 D/m + 2 on an input matrix of row dimension m + n ?, ? first m columns of the rows of M which have nonpositive ?t-degree, vol.13

, Using the assumption that ?s-reduced bases of K(F) have ?s-row degree 0 along with Item (iv) of Lemma 5.9 shows that the ?s-reduced bases of K(EF) have ?s-row degree 0. Thus, we can apply Lemma 5.13 to (EF, s, µ, ?) with µ = ? + 1 > max(s) and ? = cdeg s (EF) + 1, which is ? = cdeg s (F) + 1 according to Item (i) of Lemma 5.9

J. Abdeljaoued and G. I. Malaschonok, Efficient algorithms for computing the characteristic polynomial in a domain, Journal of Pure and Applied Algebra, vol.156, pp.127-145, 2001.

W. Baur and V. Strassen, The complexity of partial derivatives, Theoretical computer science, vol.22, pp.317-330, 1983.

B. Beckermann and G. Labahn, A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matrix Anal. Appl, vol.15, pp.804-823, 1994.

B. Beckermann, G. Labahn, and G. Villard, Shifted normal forms of polynomial matrices, ISSAC'99, ACM, pp.189-196, 1999.

B. Beckermann, G. Labahn, and G. Villard, Normal forms for general polynomial matrices, J. Symbolic Comput, vol.41, pp.708-737, 2006.
URL : https://hal.archives-ouvertes.fr/hal-02101933

S. J. Berkowitz, On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, vol.18, pp.147-150, 1984.

J. R. Bunch and J. E. Hopcroft, Triangular factorization and inversion by fast matrix multiplication, Mathematics of Computation, vol.28, pp.231-236, 1974.

P. Bürgisser, M. Clausen, and A. Shokrollahi, Algebraic Complexity Theory, 1997.

D. G. Cantor and E. Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform, vol.28, pp.693-701, 1991.

S. A. Cook, On the minimum computation time of functions, 1966.

L. Csanky, Fast parallel matrix inversion algorithms, 16th Annual Symposium on Foundations of Computer Science (sfcs 1975), pp.11-12, 1975.

A. M. Danilevskij, The numerical solution of the secular equation, Matem. Sbornik, vol.44, pp.169-171, 1937.

J. G. Dumas, C. Pernet, and Z. Sultan, Fast computation of the rank profile matrix and the generalized Bruhat decomposition, J. Symbolic Comput, vol.83, pp.187-210, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01251223

J. G. Dumas, C. Pernet, and Z. Wan, Efficient computation of the characteristic polynomial, ISSAC'05, ACM, pp.140-147, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00004056

D. S. Dummit and R. M. Foote, Abstract Algebra, 2004.

D. Faddeev and I. Sominskii, Collected Problems in Higher Algebra, Problem n979, 1949.

J. Forney and G. D. , Minimal Bases of Rational Vector Spaces, with Applications to Multivariable Linear Systems, SIAM Journal on Control, vol.13, pp.493-520, 1975.

J. Frame, A simple recurrent formula for inverting a matrix (abstract), Bull. of Amer. Math. Soc, vol.55, 1045.

J. V. Gathen and J. Gerhard, Modern Computer Algebra, 2013.

M. Giesbrecht, Nearly optimal algorithms for canonical matrix forms, SIAM Journal on Computing, vol.24, pp.948-969, 1995.

P. Giorgi, C. P. Jeannerod, and G. Villard, On the complexity of polynomial matrix computations, ISSAC'03, ACM, pp.135-142, 2003.
URL : https://hal.archives-ouvertes.fr/hal-02101878

P. Giorgi and V. Neiger, Certification of minimal approximant bases, ISSAC'18, ACM, pp.167-174, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01701861

S. Gupta, S. Sarkar, A. Storjohann, and J. Valeriote, Triangular x-basis decompositions and derandomization of linear algebra algorithms over, 2012.

, J. Symbolic Comput, vol.47, pp.422-453

D. Harvey, J. Van-der-hoeven, and G. Lecerf, Faster polynomial multiplication over finite fields, J. ACM, vol.63, 2017.
URL : https://hal.archives-ouvertes.fr/hal-02350386

O. H. Ibarra, S. Moran, and R. Hui, A generalization of the fast LUP matrix decomposition algorithm and applications, Journal of Algorithms, vol.3, pp.45-56, 1982.

C. P. Jeannerod, V. Neiger, E. Schost, and G. Villard, Fast computation of minimal interpolation bases in Popov form for arbitrary shifts, pp.295-302, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01265983

C. P. Jeannerod, V. Neiger, E. Schost, and G. Villard, Computing minimal interpolation bases, J. Symbolic Comput, vol.83, pp.272-314, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01241781

C. P. Jeannerod, V. Neiger, and G. Villard, Fast computation of approximant bases in canonical form, J. Symbolic Comput, vol.98, pp.192-224, 2020.
URL : https://hal.archives-ouvertes.fr/hal-01683632

T. Kailath, Linear Systems, 1980.

E. Kaltofen and G. Villard, On the complexity of computing determinants, Computational Complexity, vol.13, 2005.
URL : https://hal.archives-ouvertes.fr/hal-02102099

W. Keller-gehrig, Fast algorithms for the characteristic polynomial, Theoretical Computer Science, vol.36, pp.309-317, 1985.

G. Labahn, V. Neiger, and W. Zhou, Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix, J. Complexity, vol.42, pp.44-71, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01345627

L. Gall and F. , Powers of tensors and fast matrix multiplication, pp.296-303, 2014.

L. Verrier and U. , Sur les variations séculaires deséléments elliptiques des sept plantètes principales, Journal des Mathématiques Pures et Appliquées, vol.5, pp.220-254, 1840.

W. Manthey and U. Helmke, Bruhat canonical form for linear systems, Linear Algebra Appl, vol.425, pp.261-282, 2007.

T. Mulders and A. Storjohann, On lattice reduction for polynomial matrices, J. Symbolic Comput, vol.35, pp.139-145, 2003.

V. Neiger, J. Rosenkilde, and G. Solomatov, Computing Popov and Hermite Forms of Rectangular Polynomial Matrices, pp.295-302, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01701867

V. Neiger and T. X. Vu, Computing canonical bases of modules of univariate relations, ISSAC'17, ACM, pp.357-364, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01457979

C. Pernet and A. Storjohann, Faster Algorithms for the Characteristic Polynomial, ISSAC'07, ACM, pp.307-314, 2007.

V. M. Popov, Invariant description of linear, time-invariant controllable systems, SIAM Journal on Control, vol.10, pp.252-264, 1972.

P. A. Samuelson, A method of determining explicitly the coefficients of the characteristic equation, Annals of Mathematical Statistics, vol.13, pp.424-429, 1942.

S. Sarkar and A. Storjohann, Normalization of row reduced matrices, ISSAC'11, ACM, pp.297-304, 2011.

J. M. Souriau, Une méthode pour la décomposition spectrale et l'inversion des matrices, Comptes-Rendus de l'Académie des Sciences, vol.227, pp.1010-1011, 1948.

A. Storjohann, High-order lifting and integrality certification, J. Symbolic Comput, vol.36, p.97, 2003.

A. Storjohann, Notes on computing minimal approximant bases, Challenges in Symbolic Computation Software, 2006.

V. Strassen, Gaussian elimination is not optimal, Numer. Math, vol.13, pp.354-356, 1969.

F. The and . Group, FFLAS-FFPACK: Finite Field Linear Algebra Subroutines / Package, 2019.

, Linbox: Linear algebra over black-box matrices, 2019.

A. L. Toom, The complexity of a scheme of functional elements realizing the multiplication of integers, Soviet Mathematics Doklady, vol.3, pp.714-716, 1963.

M. Van-barel and A. Bultheel, A general module theoretic framework for vector M-Padé and matrix rational interpolation, Numer. Algorithms, vol.3, pp.451-462, 1992.

W. A. Wolovich, Linear Multivariable Systems, Applied Mathematical Sciences, vol.11, 1974.

W. Zhou, Fast Order Basis and Kernel Basis Computation and Related Problems, 2012.

W. Zhou and G. Labahn, Efficient computation of order bases, ISSAC'09, ACM, pp.375-382, 2009.

W. Zhou and G. Labahn, Efficient algorithms for order basis computation, J. Symbolic Comput, vol.47, pp.793-819, 2012.

W. Zhou and G. Labahn, Computing column bases of polynomial matrices, ISSAC'13, ACM, pp.379-386, 2013.

W. Zhou and G. Labahn, Unimodular completion of polynomial matrices, ISSAC'14, ACM, pp.413-420, 2014.

W. Zhou, G. Labahn, and A. Storjohann, Computing minimal nullspace bases, ISSAC'12, ACM, pp.366-373, 2012.

, If K is in ?s-Popov form, then K is in ?s-Popov form

.. .. ?-{1 and .. {1, m}, we rely on the definition of a leading matrix (see Section 2.3): the entry (i, j) of , then the entry (i, j) of lm ?s (K) is equal to L i,? . This holds, since in this case we have s j = ? ? , and by construction of K the ,? , which itself is equal to L i,? by definition of a leading matrix. Now assume K is in ?s-Popov form

, using further notation from Section 5.2: S is the basis of K(E) described in Lemma 5.8 and B = [ K S ] ? K[x] (k+m?m)×m is the basis of K(EF) given in Eq, Now we prove the claims in Remark 5.10 concerning variants of Item (iv) of Lemma 5.9

A. Lemma, With the above notation and assumptions, ? If K is in ?s-reduced form, then B is in ?s-reduced form. ? If K is in ?s-Popov form, then B is in ?s-Popov form up to row permutation