The relations between several necessary conditions for a square complex matrix A to be m-cyclic are examined. These conditions are known to be equivalent if A is an irreducible nonnegative matrix whose index of imprimitivity is m. In particular, we ยฎnd that if the digraph of A contains at least one cycle with nonzero signed length, then the following conditions are each equivalent to the m-cyclicity of A: (i) A is diagonally similar to e 2piam e; (ii) all cycles in the digraph of A have signed length an integral multiple of m. In the course of our investigations, we lay down the groundwork of the theory of cyclically m-partite or linearly partite digraphs, and characterize these digraphs in terms of the signed lengths of their cycles. The characterization of diagonal similarity between matrices in terms of matrix cycle products due to Saunders and Schneider plays a key role in our development. Our investigations also lead to a new illuminating conceptual proof for the second part of the Frobenius theorem on an irreducible nonnegative matrix. The connection between the m-cyclicity of a square complex matrix and that of its associated collection of elementary Jordan blocks is studied in the second half of this paper. In particular, for an m-cyclic collection U it is found that the problem of determining all m-tuples k 1 Y F F F Y k m of positive integers for which there exists an m-cyclic matrix A in the superdiagonal k 1 Y F F F Y k m -block form such that Ue U is equivalent to determine all row sum vectors of (0,1)-matrices that have a prescribed column sum vector and each of whose column vectors has cyclically consecutive equal components. As a by-product we also obtain an equivalent condition on m given square complex matrices f 1 Y F F F Y f m so that there exist complex rectangular matrices e 1 Y F F F Y e m that satisfy f j e j ร ร ร e m e 1 ร ร ร e jร1 for j 1Y F F F Y m, thus complet-www.elsevier.com/locate/laa