Pattern-Based Matrix Analysis Under Permutations

Low-rank approximation captures one important notion of matrix simplicity: a matrix is simple if it is well described by a low-dimensional linear model. This paper studies a complementary notion. We consider matrices that become structurally simple only after permuting rows and columns, so that their mass concentrates in a prescribed geometric pattern such as a band, block-diagonal, arrowhead, or related form. We introduce a pattern distance that measures how close a matrix is to a given structural mask after optimal reordering, giving a common framework for latent ordering, community detection, and bandwidth minimization. The problem is NP-hard in general; we derive an alternating algorithm based on Linear Assignment subproblems, and establish identifiability of the target structure up to pattern automorphisms. We further introduce a pattern-plus-low-rank decomposition that combines permutation-structured fitting with a low-rank residual; it dominates pure low-rank approximation by feasibility and admits a strict rank separation on planted block-diagonal targets, with broad empirical gains across pattern families. We evaluate the framework on synthetic recovery tasks, real correlation and graph adjacency matrices, and transformer attention heads (GPT-2, Qwen2.5-0.5B and Qwen2.5-7B), showing that a single universal algorithm recovers qualitatively different forms of matrix structure.