The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication

We present new efficient data structures for elements of Coxeter groups of type $A_m$ and their associated Iwahori--Hecke algebras $H(A_m)$. Usually, elements of $H(A_m)$ are represented as simple coefficient list of length $M = (m+1)!$ with respect to the standard basis, indexed by the elements of the Coxeter group. In the new data structure, elements of $H(A_m)$ are represented as nested coefficient lists. While the cost of addition is the same in both data structures, the ...

In [P. Niroomand, R. Rezaei, On the exterior degree of finite groups, Comm. Algebra 39 (2011), 335-343] it is introduced a group invariant, related to the number of elements $x$ and $y$ of a finite group $G$, such that $x \wedge y = 1_{G \wedge G}$ in the exterior square $G \wedge G$ of $G$. This number gives restrictions on the Schur multiplier of $G$ and, consequently, large classes of groups can be described. In the present paper we generalize the previous investigations o...

We prove an explicit formula for the tensor product with itself of an irreducible complex representation of the symmetric group defined by a rectangle of height two. We also describe part of the decomposition for the tensor product of representations defined by rectangles of heights two and four. Our results are deduced, through Schur-Weyl duality, from the observation that certain actions on triple tensor products of vector spaces, are multiplicity free.

The aim of this paper is to determine the non-abelian tensor square and Schur multiplier of groups of square free order and of groups of orders $p^2q$, $pq^2$ and $p^2qr$, where $p$, $q$ and $r$ are primes and $p<q<r$.

It is known since the 1970s that no more than 23 multiplications are required for computing the product of two 3 x 3-matrices. It is not known whether this can also be done with fewer multiplications. However, there are several mutually inequivalent ways of doing the job with 23 multiplications. In this article, we extend this list considerably by providing more than 13 000 new and mutually inequivalent schemes for multiplying 3 x 3-matrices using 23 multiplications. Moreover...

The border rank of the matrix multiplication operator for n by n matrices is a standard measure of its complexity. Using techniques from algebraic geometry and representation theory, we show the border rank is at least 2n^2-n. Our bounds are better than the previous lower bound (due to Lickteig in 1985) of 3/2 n^2+ n/2 -1 for all n>2. The bounds are obtained by finding new equations that bilinear maps of small border rank must satisfy, i.e., new equations for secant varieties...

The problems that we consider in this paper are as follows. Let A and B be 2x2 matrices (over reals). Let w(A, B) be a word of length n. After evaluating w(A, B) as a product of matrices, we get a 2x2 matrix, call it W. What is the largest (by the absolute value) possible entry of W, over all w(A, B) of length n, as a function of n? What is the expected absolute value of the largest (by the absolute value) entry in a random product of n matrices, where each matrix is A or B w...

We give an new arithmetic algorithm to compute the generalized Discrete Fourier Transform (DFT) over finite groups $G$. The new algorithm uses $O(|G|^{\omega/2 + o(1)})$ operations to compute the generalized DFT over finite groups of Lie type, including the linear, orthogonal, and symplectic families and their variants, as well as all finite simple groups of Lie type. Here $\omega$ is the exponent of matrix multiplication, so the exponent $\omega/2$ is optimal if $\omega = 2$...

We perform forward error analysis for a large class of recursive matrix multiplication algorithms in the spirit of [D. Bini and G. Lotti, Stability of fast algorithms for matrix multiplication, Numer. Math. 36 (1980), 63--72]. As a consequence of our analysis, we show that the exponent of matrix multiplication (the optimal running time) can be achieved by numerically stable algorithms. We also show that new group-theoretic algorithms proposed in [H. Cohn, and C. Umans, A grou...

The dominant theme of this thesis is the construction of matrix representations of finite solvable groups using a suitable system of generators. For a finite solvable group $G$ of order $N = p_{1}p_{2}\dots p_{n}$, where $p_{i}$'s are primes, there always exists a subnormal series: $\langle {e} \rangle = G_{o} < G_{1} < \dots < G_{n} = G$ such that $G_{i}/G_{i-1}$ is isomorphic to a cyclic group of order $p_{i}$, $i = 1,2,\dots,n$. Associated with this series, there exists a ...