Recent work has shown that fast matrix multiplication algorithms can be constructed by embedding the two input matrices into a group algebra, applying a generalized discrete Fourier transform, and performing the multiplication in the Fourier basis. Developing an embedding that yields a matrix multiplication algorithm with running time faster than naive matrix multiplication leads to interesting combinatorial problems in group theory. The crux of such an embedding, after a group G has been chosen, lies in finding a triple of subsets of G that satisfy a certain algebraic relation. I show how the process of finding such subsets can in some cases be greatly simplified by considering the action of the group G on an appropriate set X. In particular, I focus on groups acting on regularly branching trees.

This thesis is divided into two parts, each part exploring a different topic within the general area of nonlinear algebra. In the first part, we study several applications of tensors. First, we study tensor networks, and more specifically: uniform matrix product states. We use methods from nonlinear algebra and algebraic geometry to answer questions about topology, defining equations, and identifiability of uniform matrix product states. By an interplay of theorems from algebra, geometry, and quantum physics we answer several questions and conjectures posed by Critch, Morton and Hackbusch. In addition, we prove a tensor version of the so-called quantum Wielandt inequality, solving an open problem regarding the higher-dimensional version of matrix product states. Second, we present new contributions to the study of fast matrix multiplication. Motivated by the symmetric version of matrix multiplication we study the plethysm S^k(sl_n) of the adjoint representation sl_n of the Lie group SL_n . Moreover, we discuss two algebraic approaches for constructing new tensors which could potentially be used to prove new upper bounds on the complexity of matrix multiplication. One approach is based on the highest weight vectors of the aforementioned plethysm. The other approach uses smoothable finite-dimensional algebras. Finally, we study the Hessian discriminant of a cubic surface, a recently introduced invariant defined in terms of the Waring rank. We express the Hessian discriminant in terms of fundamental invariants. This answers Question 15 of the 27 questions on the cubic surface posed by Bernd Sturmfels. In the second part of this thesis, we apply algebro-geometric methods to study matroids and flag matroids. We review a geometric interpretation of the Tutte polynomial in terms of the equivariant K-theory of the Grassmannian. By generalizing Grassmannians to partial flag varieties, we obtain a new invariant of flag matroids: the flag-geometric Tutte polynomial. We study this invariant in detail, and prove several interesting combinatorial properties.

Based on Cohn and Umans’ group-theoretic method, we embed matrix multiplication into several group algebras, including those of cyclic groups, dihedral groups, special linear groups and Frobenius groups. We prove that SL2(Fp) and PSL2(Fp) can realize the matrix tensor ⟨p, p, p⟩, i.e. it is possible to encode p × p matrix multiplication in the group algebra of such a group. We also find the lower bound for the order of an abelian group realizing ⟨n, n, n⟩ is n3. For Frobenius groups of the form Cq Cp, where p and q are primes, we find that the smallest admissible value of q must be in the range p4/3 ≤ q ≤ p2 − 2p + 3. We also develop an algorithm to find the smallest q for a given prime p.