Identifying Kronecker product factorizations

The Kronecker product is an invaluable tool for data-sparse representations of large networks and matrices with countless applications in machine learning, graph theory, and numerical linear algebra. In some instances, the sparsity pattern of large matrices may already hide a Kronecker product. Similarly, a large network, represented by its adjacency matrix, may sometimes be factorized as a Kronecker product of smaller adjacency matrices. In this article, we determine all possible Kronecker factorizations of a square binary matrix by combining simpler factorizations of only two binary matrices. We then define a decomposition graph for conveniently visualizing the number of factors as well as their sizes. Such sparsity-informed factorizations may later enable good (approximate) Kronecker factorizations of real square matrices or reveal the latent structure of a network. The latter also suggests a natural visualization of Kronecker graphs.