Normalization of row reduced matrices
Soumojit Sarkar, Arne Storjohann · 2011
This paper gives gives a deterministic algorithm to transform a row reduced matrix to canonical Popov form. Given as input a row reduced matrix R over K[x], K a field, our algorithm computes the Popov form in about the same time as required to multiply together over K[x] two matrices of the same dimension and degree as R. We also show that the problem of transforming a row reduced matrix to Popov form is at least as hard as polynomial matrix multiplication.