An \(NC^ 2\) algorithm for testing similarity of matrices (Q1116651)

The authors make the observation that there is a fast parallel deterministic algorithm for deciding when two square matrices A and B (over an arbitrary field) are similar. Indeed, the reviewer showed that A and B are similar if and only if \(r(A,B)^ 2=r(A,A)r(B,B)\) where r(A,B) denotes the rank of \(A\otimes I-I\otimes B\) and I is the identity matrix [cf. the reviewer, Linear and Multilinear Algebra 8, 69-72 (1979; Zbl 0432.13009)] and \textit{K. Mulmuley} [Combinatorica 7, 101-104 (1987; Zbl 0635.65040)] has shown that there is a fast parallel algorithm for computing the rank.