Properties of unilevel block circulants

Let , and .All operations in indices are modulo k.It is well known that if d1=d2=1 then , where .However, to our knowledge it has not been emphasized that FA plays a fundamental role in connection with all the matrices , with d1,d2 arbitrary.We begin by adapting a theorem of Ablow and Jenner with d1=d2=1 to the case where d1 and d2 are arbitrary.We show that if and only if A=UαFAP∗ where Uα and P are related to Φ,P is unitary, and Uα is invertible (in fact, unitary) if and only if gcd(α,k)=1, in which case we say that A is a proper circulant.We prove the following for proper circulants :(i) with .(ii) Solving Az=w reduces to solving Fℓuℓ=vαℓ,0⩽ℓ⩽k-1, where v0,v1,…,vk-1 depend only on w.(iii) A singular value decomposition of A can be obtained from singular value decompositions ofF0,F1,…,Fk-1. (iv) The least squares problem for A reduces to independent least squares problems for F0,F1,…,Fk-1. (v) If d1=d2=d, the eigenvalues of are the eigenvalues of F0,F1,…,Fk-1, and the corresponding eigenvectors of A are easily obtainable from those of F0,F1,…,Fk-1. (vi) If d1=d2=d and α>1 then the eigenvalue problem for reduces to eigenvalue problems for d×d matrices related to F0,F1,…,Fk-1 in a manner depending upon α.