An \(NC^ 2\) algorithm for testing similarity of matrices (Q1116651)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An \(NC^ 2\) algorithm for testing similarity of matrices |
scientific article |
Statements
An \(NC^ 2\) algorithm for testing similarity of matrices (English)
0 references
1989
0 references
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.
0 references
similarity of matrices
0 references
parallel deterministic algorithm
0 references
fast parallel algorithm
0 references
0 references
0 references
0 references