We conjecture that under the permutation similar equivalence relation there are exactly φ(k) solutions A to the matrix equation A k =J d k + 1 -I d k + 1 , where φ is Euler's totient function, d>1 is an integer, k>0 is an odd integer, J is the matrix of all ones, I is the identity matrix, and A is an unknown (0,1) matrix. We present an approach to verify this conjecture. It establishes a connection between the work of solving the matrix equation A k =J-I and the problems of both determining the structure of near-k-factor factorizations of cyclic groups and characterizing cycle-powers. We also collect some results about the latter two problems in order to give more insight into this approach.