We show that the Hamiltonicity of a regular graph can be fully
characterized by the numbers of blocks of consecutive ones in the
binary matrix A+I, where A is the adjacency matrix of the graph, I the
unit matrix, and the blocks can be either linear or circular. For the
problem of determining whether a given matrix can have at most k blocks
of consecutive ones per column by some row permutation, we prove that
it remains NP-complete for every constant k >= 2 even if the matrix is
restricted to (1) symmetric, or (2) having at most three blocks per
row. (This is joint work with Rui Wang)