  We investigate a principled approach for symbolic operation completion (SOC),
a minimal task for studying symbolic reasoning. While conceptually similar to
matrix completion, SOC poses a unique challenge in modeling abstract
relationships between discrete symbols. We demonstrate that SOC can be
efficiently solved by a minimal model - a bilinear map - with a novel
factorized architecture. Inspired by group representation theory, this
architecture leverages matrix embeddings of symbols, modeling each symbol as an
operator that dynamically influences others.
  Our model achieves perfect test accuracy on SOC with comparable or superior
sample efficiency to Transformer baselines across most datasets, while boasting
significantly faster learning speeds (100-1000$\times$). Crucially, the model
exhibits an implicit bias towards learning general group structures, precisely
discovering the unitary representations of underlying groups. This remarkable
property not only confers interpretability but also significant implications
for automatic symmetry discovery in geometric deep learning.
  Overall, our work establishes group theory as a powerful guiding principle
for discovering abstract algebraic structures in deep learning, and showcases
matrix representations as a compelling alternative to traditional vector
embeddings for modeling symbolic relationships.
