Effective Algorithms for Decomplexifying a Matrix by Unitary Similarities or Congruences

It is required to verify whether a given complex $n\times 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=\overline 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.