Effective algorithms for decomplexifying a matrix by unitary similarities or congruences

It is required to verify whether a given complex n × n matrix A can be made real by a similarity or a congruence transformation. Algorithms for solving these two problems are proposed and justified under the additional assumption that A is irreducible in the former case and $A_L = \bar AA$ is irreducible in the latter case. The irreducibility of a square complex matrix means that no unitary similarity transformation converts this matrix into a direct sum of smaller matrices. The proposed algorithms are effective in the sense that their implementation requires a finite number of arithmetic operations.