First off it should be obvious that cyclic matrix on A vector (i.e. matrix where first row is A₁A₂...A_N, second row is A₂A₃...A_NA₁ and so on) should have zero determinant. There is a theorem that determinant of cyclic matrix is product of values of f in roots of one of order N, where f = A₁ + A₂x + A₃x² + ... + A_Nx^N - 1, so in order for it to be zero one of those roots of one should be root of this polynom as well. But if one of them is root then it's conjugate is root as well, hence we only need to check whether f is divisible by x² - 2a + 1, where a is real part of root