Length function and simultaneous triangularization of matrix pairs

The present paper links the simultaneous triangularization problem for matrix pairs with the Paz problem and known results on the length of the matrix algebra. The length function is applied to the Al'pin–Koreshkov algorithm, and it is demonstrated how to reduce its multiplicative complexity. An asymptotically better procedure for verifying the simultaneous triangularizability of a pair of complex matrices is provided. This procedure is based on results on the lengths of upper triangular matrix algebras. Also the definition of hereditary length of an algebra is introduced, and the problem of computing the hereditary lengths of matrix algebras is discussed.