An approach to solving \(A^{k}=J-I\) (Q1414133)

The authors consider the matrix equation \(A^k=J_{d^k+1}-I_{d^k+1}~(*)\) where \(d>1\) is an integer, \(k>0\) is an odd integer, \(J\) is the all-one matrix, \(I\) is the identity matrix, and \(A\) is an unknown \((0,1)\) matrix. The equation (with \(k=3\)) arises from problems concerning digraphs and their walks of length \(3\) connecting two given vertices. The authors conjecture that under the permutation similar equivalence relation there are exactly \(\varphi (k)\) solutions \(A\) to \((*)\) where \(\varphi (k)\) is Euler's totient function (the number of positive integers less than and relatively prime to \(k\)). An approach to verify the conjecture is proposed which establishes a connection between the work on solving the matrix equation \(A^k=J-I\) and the problems of determining the structure of near-\(k\)-factor factorization of cyclic groups and characterizing cycle-powers. Some results are collected about the latter two problems in order to give a better understanding of the approach.