# On the local dimensions of solutions of Brent equations

Xin Li  Department of Mathematics, Zhejiang University of Technology, Hangzhou
310023, P. R. China<EMAIL_ADDRESS>(X. Li) ,  Yixin Bao  School of
Sciences, Harbin Institute of Technology, Shenzhen, 518055, China
mabaoyixin19840163.com (Y. Bao) and  Liping Zhang  Department of Mathematics,
Zhejiang University of Technology, Hangzhou 310023, P. R. China
<EMAIL_ADDRESS>(L. Zhang)

###### Abstract.

Let $\langle m,n,p\rangle$ be the matrix multiplication tensor. The solution
set of Brent equations corresponds to the tensor decompositions of $\langle
m,n,p\rangle$. We study the local dimensions of solutions of the Brent
equations over the field of complex numbers. The rank of Jacobian matrix of
Brent equations provides an upper bound of the local dimension, which is well-
known. We calculate the ranks for some typical known solutions, which are
provided in the databases [16] and [17]. We show that the automorphism group
of the natural algorithm computing $\langle m,n,p\rangle$ is
$(\mathcal{P}_{m}\times\mathcal{P}_{n}\times\mathcal{P}_{p})\rtimes Q(m,n,p)$,
where $\mathcal{P}_{m}$, $\mathcal{P}_{n}$ and $\mathcal{P}_{p}$ are groups of
generalised permutation matrices, $Q(m,n,p)$ is a subgroup of $S_{3}$
depending on $m$, $n$ and $p$. For other algorithms computing $\langle
m,n,p\rangle$, a condition is given, which implies the corresponding
automorphism groups are isomorphic to subgroups of
$(\mathcal{P}_{m}\times\mathcal{P}_{n}\times\mathcal{P}_{p})\rtimes Q(m,n,p)$.
So under this condition, $m^{2}+n^{2}+p^{2}-m-n-p-3$ is a lower bound for the
local dimensions of solutions of Brent equations.

###### Key words and phrases:

Brent equations, Local dimension, Jacobian matrix, Automorphism group, Matrix
multiplication tensor

###### 2010 Mathematics Subject Classification:

Primary 14L30; Secondary 68Q17

##  1\. Introduction

The solution set $V$ of a system of polynomial equations may contain points,
curves, surfaces, etc., each with its own dimension. A fundamental problem
when working with such systems is to describe these (local) dimensions [1].
Let $V$ be an affine variety and $q\in V$. The _local dimension_ of $q$ is
defined by the maximum dimension of an irreducible component of $V$ containing
$q$ [10].

In this paper, we give estimations for the local dimensions of the solution
set of _the Brent equations_ [4, 18, 22, 27]. Since the Brent equations
contain a huge number of equations and variables, it is hard to calculated the
local dimensions explicitly by current methods, such as [1, 23]. So in this
paper, we study the upper and lower bounds of the local dimensions. Firstly,
by the Jacobian Criterion of [14, Theorem 4.1.12], we calculate the upper
bound of local dimensions for some typical points, which are provided in the
databases [16] and [17]. Secondly, by the theory of linear algebraic groups,
we get the lower bound of local dimensions [5, Proposition 1.11]. Other
methods for the estimation of local dimensions can be found in [3].

Let $\langle m,n,p\rangle$ denote the well-known matrix multiplication tensor
(see e.g. [8, 13, 18, 22]). The tensor decomposition of $\langle m,n,p\rangle$
of length $r$ gives rise to the Brent equations [18, 27] (see also Section
3.1). We denote it by $B(m,n,p;r)$. The solution set of $B(m,n,p;r)$ in the
field of complex number is denoted by $V(m,n,p;r)$. For a point $q\in
V(m,n,p;r)$, let $\dim_{q}V(m,n,p;r)$ denote its local dimension. Let
$J_{q}(B(m,n,p;r))$ denote the Jacobian matrix of $B(m,n,p;r)$ at $q$ and
$rank~{}J_{q}(B(m,n,p;r))$ its rank. The Jacobian Criterion implies

$\dim_{q}V(m,n,p;r)\leq k-rank~{}J_{q}(B(m,n,p;r))$

where $k=(mn+np+pm)r$. In Section 3.1.1, we calculated
$rank~{}J_{q}(B(3,3,3;23))$ and $rank~{}J_{q^{\prime}}(B(4,4,4;49))$, where
$q$ and $q^{\prime}$ are the solutions summarized in the databases [16] and
[17]. So we can get upper bounds of local dimensions of these points. For the
solutions provided in the database [17], the distribution of
$rank~{}J_{q}(B(3,3,3;23))$ is summarized in Table 1 and 2 of Section 3.1.1.
We can see that the upper bounds given by the Jacobian Criterion for Brent
equations are meaningful, because the ranks of $rank~{}J_{q}(B(3,3,3;23))$ and
$rank~{}J_{q^{\prime}}(B(4,4,4;49))$ are big.

On the other hand, the isotropy group of $\langle m,n,p\rangle$ induces a
group action on $V(m,n,p;r)$ [11, 12, 13]. By the theory of linear algebraic
groups [5, Proposition 1.11], we get a lower bound for local dimensions of
points in $V(m,n,p;r)$. Let $\mathcal{A}(m,n,p)=\\{e_{ij}\otimes e_{jk}\otimes
e_{ki}|1\leq i\leq m,1\leq j\leq n,1\leq k\leq p\\}$ denote the _natural
algorithm_ computing $\langle m,n,p\rangle$. We show that the automorphism
group of $\mathcal{A}(m,n,p)$ is
$(\mathcal{P}_{m}\times\mathcal{P}_{n}\times\mathcal{P}_{p})\rtimes Q(m,n,p)$,
where $\mathcal{P}_{m}\subseteq GL_{m}(\mathbb{C})$ is the generalised
permutation groups (similarly, for $\mathcal{P}_{n}$ and $\mathcal{P}_{p}$),
$Q(m,n,p)$ is a subgroup of $S_{3}$ depending on $m,n,p$ (see Corollary 3.11).
A condition (see Definition 3.7) is given which implies that the automorphism
group of an algorithm computing $\langle m,n,p\rangle$ is (isomorphic to) a
subgroup of
$(\mathcal{P}_{m}\times\mathcal{P}_{n}\times\mathcal{P}_{p})\rtimes Q(m,n,p)$
(see Corollary 3.10). So under this condition, we obtain a lower bound for
local dimensions for points $q$ in $V(m,n,p;r)$ (see Corollary 3.14):

$\dim_{q}V(m,n,p;r)\geq m^{2}+n^{2}+p^{2}-m-n-p-3.$

Moreover, we find that the polynomial ideals generated by Brent equations may
not be radical. The ranks of Jacobian matrices may serve as invariants to
distinguish group orbits.

The paper is organized as follows. In Section 2, the preliminaries about local
dimension are recalled, which are the Jacobian Criterion and the property for
the dimension of group orbits. The main results are given in Section 3.

##  2\. Upper and lower bounds of the local dimensions

###  2.1. Rank of Jacobian matrix and the upper bound

Let $\mathbb{C}$ denote the field of complex numbers and $\mathbb{C}^{n}$ the
$n$-dimensional complex vector space. Let $A=\mathbb{C}[x_{1},...,x_{n}]$ be
the polynomial ring in $n$ variables over $\mathbb{C}$. If $T$ is any subset
of $A$, set

$V(T)=\\{p\in\mathbb{C}^{n}|f(p)=0~{}for~{}all~{}f\in T\\}$

to be the common zeros of all the elements of $T$.

######  Definition 2.1.

A subset $Y$ of $\mathbb{C}^{n}$ is an affine variety if there exists a subset
$T\subseteq A$ such that $Y=V(T)$.

######  Remark 2.2.

In literatures, $Y$ is also called an algebraic set (see e.g. [14]). Here we
follow the definition of [10].

Thus, the solution set $V$ of a system of polynomial equations is an affine
variety. Given a point $p$ on the affine variety
$V=\\{x\in\mathbb{C}^{n}|F(x)=0\\}$ for a set of polynomials
$F(x)=\\{f_{1}(x),...,f_{m}(x)\\}\subseteq\mathbb{C}[x_{1},...,x_{n}]$. The
Jacobian matrix of $F$ at a point $p\in\mathbb{C}^{n}$ is defined by

$J_{p}(F)=J_{p}(f_{1},f_{2},...,f_{m})=\left(\begin{array}[]{ccc}\frac{\partial
f_{1}}{\partial x_{1}}(p)&\cdots&\frac{\partial f_{1}}{\partial x_{n}}(p)\\\
\vdots&{}\hfil&\vdots\\\ \frac{\partial f_{m}}{\partial
x_{1}}(p)&\cdots&\frac{\partial f_{m}}{\partial x_{n}}(p)\\\
\end{array}\right)_{m\times n}$

The _vanishing ideal_ of $V$ is given by the set

$I(V)=\\{f\in\mathbb{C}[x_{1},...,x_{n}]|~{}f(a)=0~{}\text{for all}~{}a\in
V\\},$

which is a radical ideal. Let $\langle f_{1},f_{2},...,f_{m}\rangle$ denote
the ideal generated by $f_{1},f_{2},...,f_{m}$ in
$\mathbb{C}[x_{1},...,x_{n}]$. Then $I(V)$ is the radical of $\langle
f_{1},f_{2},...,f_{m}\rangle$. So $\langle f_{1},f_{2},...,f_{m}\rangle$ may
be strictly contained in $I(V)$. Let $T_{p}(V)$ denote the tangent space of
$p$ at $V$ (see Definition 4.1.6 of [14]). If $I(V)$ is generated by
$\\{g_{1},g_{2},...,g_{r}\\}$, then by Remark 4.1.7 of [14] we know that

$\dim T_{p}(V)=n-rank~{}J_{p}(g_{1},g_{2},...,g_{r}).$

For an affine variety $V$ which is defined by $F=\\{f_{1},f_{2},...,f_{m}\\}$,
we have the following upper bound on the local dimension of a point $p\in V$,
which is called _Jacobian Criterion_ in [14].

######  Theorem 2.3.

[14, Theorem 4.1.12, Jacobian Criterion] Let $p$ be a point on an affine
variety $V\in\mathbb{C}^{n}$. Then

$\dim_{p}V\leq\dim T_{p}(V)\leq n-rank~{}J_{p}(F).$

In Section 3, when $F$ is the Brent equations, using computer we will
calculate $J_{p}(F)$ for some typical known solutions. So they give the upper
bounds of local dimensions for these solutions.

###  2.2. Isotropy group orbit and the lower bound

In this section, we recall some results of [5] and [13].

A $G$-variety is an affine variety $X$ equipped with an action of the
algebraic group $G$. Given a $G$-variety $X$ and a point $x\in X$, the orbit
$G\cdot x\subseteq X$ is the set of all $g\cdot x$, where $g\in G$. The
automorphism group (it was called the isotropy group in [5]) $G_{x}\subseteq
G$ is the set of those $g\in G$ such that $g\cdot x=x$; it is a closed
subgroup of $G$.

######  Proposition 2.4.

[5, Proposition 1.11] The group orbit $G\cdot x$ is a locally closed, smooth
subvariety of $X$, and every component of $G\cdot x$ has dimension
$\dim(G)-\dim(G_{x})$.

A group $G$ is said to be a _semidirect product_ of $A$ by $B$, which is
denoted by $G=A\rtimes B$, if $G=AB$, $A\unlhd G$ ($A$ is a normal subgroup of
$G$) and $A\cap B=1$. If $A$ is a subgroup (or isomorphic to a subgroup) of
$G$, then it will be denoted by $A\leq G$. Let $PGL_{n}(\mathbb{C})$ and
$\mathcal{D}_{n}\subseteq GL_{n}(\mathbb{C})$ denote the projective general
linear group and the group of nonsigular diagonal matrices over $\mathbb{C}$,
respectively. Let $S_{n}$ denote the symmetric group of order $n$. For the
dimension of algebraic groups, we have the following proposition. They can be
found in Section 1.8 and 5.5 of [28] and [24].

######  Proposition 2.5.

Suppose that $G$, $H$ are algebraic groups. Then

  1. (1)

$\dim G=0$ if $G$ is a finite group;

  2. (2)

$\dim(G\times H)=\dim(G\rtimes H)=\dim G+\dim H$;

  3. (3)

In particular, $\dim PGL_{n}(\mathbb{C})=n^{2}-1$;

  4. (4)

$\dim((PGL_{m}(\mathbb{C})\times PGL_{n}(\mathbb{C})\times
PGL_{p}(\mathbb{C}))\rtimes S_{3})=m^{2}+n^{2}+p^{2}-3$;

  5. (5)

$\dim(\mathcal{D}_{n}\rtimes S_{n})=n$.

Let $U$, $V$, $W$ be finite dimensional vector spaces over $\mathbb{C}$ and
$\Phi:~{}U\times V\to W$ a bilinear mapping. Let $t\in U^{*}\otimes
V^{*}\otimes W$ be the structure tensor of $\Phi$ . According to some choice
of bases in $U$, $V$, $W$, let $t_{\lambda\mu\nu}$ be the coordinates of $t$,
where $\lambda=1,...,\dim U$; $\mu=1,...,\dim V$; $\nu=1,...,\dim W$. Suppose
that $t$ has a tensor (or decomposable) decomposition of length $R$. That is,
$t=\sum_{i=1}^{R}u_{i}\otimes v_{i}\otimes w_{i}$ where
$u_{i}=(u_{i\lambda})\in U$, $v_{i}=(v_{i\mu})\in V$, $w_{i}=(w_{i\nu})\in W$.
It means the following polynomial system has solutions:

$t_{\lambda\mu\nu}-\sum_{i=1}^{R}u_{i\lambda}v_{i\mu}w_{i\nu}=0.$ (2.1)

Let $\mathfrak{a}_{R}(\Phi)$ denote the set of all solutions which is an
affine variety. It was called the _algorithm variety_ of $\Phi$ [13]. In
particular, if $\Phi$ is the matrix multiplication, then the polynomial system
(2.1) is called _the Brent equations_ (see an explicit description in equation
(3.3)).

If some linear transformation $\varphi\in End(U^{*}\otimes V^{*}\otimes W)$
leaves the tensor $t$ of $\Phi$ fixed, i.e. $\varphi(t)=t$, then it induces a
transformation (denoted by $\hat{\varphi}$):
$\hat{\varphi}:\mathfrak{a}_{R}(\Phi)\to\mathfrak{a}_{R}(\Phi)$. In
particular, let

$H=\\{\varphi|~{}\varphi(t)=t~{}\text{and}~{}\varphi\in GL(U^{*}\otimes
V^{*}\otimes W)\\}.$

Then $H\leq GL(U^{*}\otimes V^{*}\otimes W)$ is called _the isotropy group_ of
$t$. The transformation $\hat{\varphi}$ induced by $\varphi\in H$ is a group
action on the affine variety $\mathfrak{a}_{R}(\Phi)$. For a point
$x\in\mathfrak{a}_{R}(\Phi)$, if we know the dimension of the automorphism
group $H_{x}$ and $H$, then with these notations, by Proposition 2.4 we have
the following proposition

######  Proposition 2.6.

For $x\in\mathfrak{a}_{R}(\Phi)$, the local dimension of $x$ is greater than
$\dim H-\dim H_{x}$.

In particular, if $\Phi$ is the matrix multiplication and $H$ the isotropy
group studied in [11, 12] and [8], then in Section 3.2 we will study the
structure of $H_{x}$. A lower bound of local dimensions of points in
$\mathfrak{a}_{R}(\Phi)$ (the solution of Brent equations) will be given.

###  2.3. Rank of the Jacobian matrix as an invariant

Suppose that $V$ is an affine variety and $G$ is an algebraic group which acts
on $V$. If we know the generators of the radical ideal $I(V)$, then by the
following proposition we can see that the rank of Jacobian matrix of the
generators is an invariant to distinguish group orbits.

######  Proposition 2.7.

[14, Cor. 4.1.18] If $\varphi:A\to B$ is an isomorphism of affine varieties
and $p\in A$ is a point, then

$d_{p}\varphi:T_{p}A\to T_{\varphi(p)}B$

is an isomorphism of $\mathbb{C}$-vector spaces.

######  Corollary 2.8.

Suppose that $V\subseteq\mathbb{C}^{n}$ is an affine variety and $G\subseteq
GL_{n}(\mathbb{C})$ is an algebraic group which acts on $V$. Suppose that
$I(V)$ is generated by
$\\{f_{1},f_{2},...,f_{m}\\}\subseteq\mathbb{C}[x_{1},x_{2},...,x_{n}]$. Let
$p,q\in V$ be two points. If $rank~{}J_{p}(f_{1},f_{2},...,f_{m})\neq
rank~{}J_{q}(f_{1},f_{2},...,f_{m})$, then $p$ and $q$ can not lie in the same
group orbit of $G$.

###### Proof.

In Proposition 2.7, if we let $A=B=V$, then the group action of $G$ induces an
isomorphism of $V$. So if $p$ and $q$ lie in the same group orbit of $G$, we
have $\dim T_{p}V=\dim T_{q}V$. The proof is completed by $\dim
T_{p}V=n-rank~{}J_{p}(f_{1},f_{2},...,f_{m})$ for all $p\in V$. ∎

##  3\. The local dimensions of solutions of Brent equations

In this section, we use the definitions and symbols of [8]. Let $V_{1}$,
$V_{2}$, $V_{3}$ be vector spaces over $\mathbb{C}$. Denote their tensor
product by $\tilde{V}=V_{1}\otimes V_{2}\otimes V_{3}$. A tensor
$t\in\tilde{V}$ is _decomposable_ if $t=v_{1}\otimes v_{2}\otimes v_{3}$ where
$v_{i}\in V_{i}$. If a tensor $t\in\tilde{V}$ can be written as

$t=t_{1}+t_{2}+\cdots+t_{r}$

where $t_{i}$ are decomposable tensors, we call $t$ has a _tensor
decomposition of length $r$._ The set $\\{t_{1},...,t_{r}\\}$ is called _an
algorithm of length $r$ computing $t$_. The minimal length computing $t$ is
called the _tensor rank_ of $t$.

###  3.1. Brent equations and the upper bound

In particular, let $V_{1}=\mathbb{C}^{m\times n}$, $V_{2}=\mathbb{C}^{n\times
p}$ and $V_{3}=\mathbb{C}^{p\times m}$ denote the set of complex $m\times n$,
$n\times p$ and $p\times m$ matrices, respectively. The matrix multiplication
tensor is defined by (see e.g. [8, 22])

$\langle m,n,p\rangle=\sum_{i=1}^{m}\sum_{j=1}^{n}\sum_{k=1}^{p}e_{ij}\otimes
e_{jk}\otimes e_{ki}\in\mathbb{C}^{m\times n}\otimes\mathbb{C}^{n\times
p}\otimes\mathbb{C}^{p\times m},$ (3.1)

where $e_{ij}$ denotes the matrix with its coefficient at the intersection of
row $i$ and column $j$ equal to 1 and all its other coefficients equal to 0.
So equation (3.1) provides an algorithm of length $mnp$ computing $\langle
m,n,p\rangle$. Starting from the famous work of Strassen [29], finding
possible tensor decomposition of $\langle m,n,p\rangle$ with length less than
$mnp$ is an important topic in algebraic complexity theory [6, 13, 22]. It is
equivalent to find solutions of a system of polynomial equations called the
_Brent equations_ , which was firstly observed by Brent [4].

The Brent equations are given as follows (see also e.g. [8, 18, 27]). To find
a tensor decomposition of $\langle m,n,p\rangle$ of length $r$, it means that

$\langle m,n,p\rangle=t_{1}+t_{2}+\cdots+t_{r},$ (3.2)

where $t_{i}=u_{i}\otimes v_{i}\otimes w_{i}$ and

$u_{i}=\left(\alpha_{i_{1},i_{2}}^{(i)}\right)\in\mathbb{C}^{m\times
n},v_{i}=\left(\beta_{j_{1},j_{2}}^{(i)}\right)\in\mathbb{C}^{n\times
p},w_{i}=\left(\gamma_{k_{1},k_{2}}^{(i)}\right)\in\mathbb{C}^{p\times m}.$

Here $\alpha_{i_{1},i_{2}}^{(i)}$, $\beta_{j_{1},j_{2}}^{(i)}$ and
$\gamma_{k_{1},k_{2}}^{(i)}$ are unknown variables. Then by (3.1) and (3.2) we
obtain the Brent equations which correspond to the tensor decomposition of
$\langle m,n,p\rangle$ of length $r$:

$\sum_{i=1}^{r}\alpha_{i_{1},i_{2}}^{(i)}\beta_{j_{1},j_{2}}^{(i)}\gamma_{k_{1},k_{2}}^{(i)}=\delta_{i_{2},j_{1}}\delta_{j_{2},k_{1}}\delta_{k_{2},i_{1}},$
(3.3)

where $k_{2},i_{1}\in\\{1,2,...,m\\}$, $i_{2},j_{1}\in\\{1,2,...,n\\}$,
$j_{2},k_{1}\in\\{1,2,...,p\\}$ and $\delta_{ij}$ is the Kronecker symbol.

In the following, we denote the Brent equations in (3.3) by $B(m,n,p;r)$. From
(3.3), we can see that the polynomial system $B(m,n,p;r)$ has $(mnp)^{2}$
equations and $(mn+np+pm)r$ variables. So it is a large polynomial system even
when $m,n,p$ are small. Usually, $B(m,n,p;r)$ is an overdetermined polynomial
system. For example, $B(3,3,3;23)$ (resp. $B(4,4,4;49)$) has 729 (resp. 4096)
equations and 621 (resp. 2352) variables. The solution set of $B(m,n,p;r)$
over $\mathbb{C}$ is denoted by $V(m,n,p;r)$.

####  3.1.1. The numerical statistics of ranks of $J_{p}(B(3,3,3;23))$ and
$J_{p}(B(4,4,4;49))$

In this subsection, we calculate the ranks of Jacobian matrices of points in
$V(3,3,3;23)$ and $V(4,4,4;49)$, which are provided in [17] and [16]. Then by
Theorem 2.3, we get upper bounds of local dimensions for these points. We
mainly focused on points of $V(3,3,3;23)$ provided in [17].

In [17], Heule et al. provided 17376 points in $V(3,3,3;23)$ (they are called
“schemes” in [17]). Using computer, we calculated the ranks of Jacobian
matrices of $B(3,3,3;23)$ at these points. We summarize the results in Table 1
and 2. For points $p\in V(3,3,3;23)$ provided in [17], the first rows of Table
1 and 2 are the ranks of $J_{p}(B(3,3,3;23))$. The second rows are the upper
bound of local dimensions provided in Theorem 2.3, that is,
$621-J_{p}(B(3,3,3;23))$. The third rows are total number of points that have
the rank among all 17376 points. Take the first column of Table 1 as an
example. The first number 526 is the rank of Jacobian matrix at some points in
$V(3,3,3;23)$, which are provided in [17]. The second number is 621-526=95,
which is an upper bound of local dimensions for these points. The third number
5 is the number of points that have the rank 526 among all 17376 points.

Rank | 526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535
---|---|---|---|---|---|---|---|---|---|---
Upper bound | 95 | 94 | 93 | 92 | 91 | 90 | 89 | 88 | 87 | 86
Total number | 5 | 25 | 79 | 256 | 624 | 1421 | 2250 | 3069 | 3486 | 2870
Table 1. Part I Rank | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545
---|---|---|---|---|---|---|---|---|---|---
Upper bound | 85 | 84 | 83 | 82 | 81 | 80 | 79 | 78 | 77 | 76
Total number | 1709 | 858 | 387 | 159 | 73 | 68 | 25 | 7 | 2 | 3
Table 2. Part II

We also calculated ranks of Jacobian matrices for points in $V(4,4,4;49)$,
that are provided in [16]. Fawzi et al. provided 14236 points. By computation,
we find that the ranks of $J_{p}(B(4,4,4;49))$ are range from 2144 to 2201. So
the upper bounds of local dimensions for these points are range from 151 to
208. Moreover, we find that the rank of $J_{p}(B(4,4,4;49))$ equal to 2155 for
13530 points, which takes the percentage of 95$\%$.

###  3.2. Automorphism groups of $\langle m,n,p\rangle$ and the lower bound

Let $S(V_{1},V_{2},V_{3})$ denote the group of all _decomposable
automorphisms_ of $\tilde{V}=V_{1}\otimes V_{2}\otimes V_{3}$. Let
$S^{0}(V_{1},V_{2},V_{3})$ denote the subgroup of $S(V_{1},V_{2},V_{3})$
consisting of all decomposable automorphisms that preserve each factor
$V_{i}$. The set of all decomposable automorphisms of $\tilde{V}$ that
preserve $t$ is called _the (full) isotropy group_ of $t$, which is denoted by
$\Gamma(t)$:

$\Gamma(t)=\\{g\in S(V_{1},V_{2},V_{3})|g(t)=t\\}.$

The _small_ isotropy group of $t$ is defined by

$\Gamma^{0}(t)=\Gamma(t)\cap S^{0}(V_{1},V_{2},V_{3}).$

From Corollary V.5 of [13], we have $\Gamma^{0}(t)\unlhd\Gamma(t)$ and
$\Gamma(t)/\Gamma^{0}(t)$ is a subgroup of $S_{3}$.

Let $\mathcal{A}=\\{t_{1},...,t_{r}\\}$ be an algorithm computing $t$. Then

$Aut(\mathcal{A})=\\{g\in\Gamma(t)|g(\mathcal{A})=\mathcal{A}\\}$

is called _the automorphism group_ of $\mathcal{A}$, which is a subgroup of
$\Gamma(t)$. The _small_ automorphism group of $\mathcal{A}$ is defined by

$Aut(\mathcal{A})_{0}=Aut(\mathcal{A})\cap\Gamma^{0}(t).$

Since $\Gamma^{0}(t)\unlhd\Gamma(t)$ and $Aut(\mathcal{A})\leq\Gamma(t)$, by
the second isomorphism theorem of groups (see e.g. Theorem 2.26 of [25]) we
have $Aut(\mathcal{A})_{0}\unlhd Aut(\mathcal{A})$ and

$Aut(\mathcal{A})/Aut(\mathcal{A})_{0}=Aut(\mathcal{A})/(Aut(\mathcal{A})\cap\Gamma^{0}(t))\cong(Aut(\mathcal{A})\Gamma^{0}(t))/\Gamma^{0}(t)\leq\Gamma(t)/\Gamma^{0}(t)\leq
S_{3}.$

In the following, let $t=\langle m,n,p\rangle$. We will give an upper bound of
$Aut(\mathcal{A})$ (see Corollary 3.10). Recall that

$\langle m,n,p\rangle=\sum_{i=1}^{m}\sum_{j=1}^{n}\sum_{k=1}^{p}e_{ij}\otimes
e_{jk}\otimes e_{ki}\in\mathbb{C}^{m\times n}\otimes\mathbb{C}^{n\times
p}\otimes\mathbb{C}^{p\times m}.$

######  Definition 3.1.

We call $\mathcal{A}(m,n,p)=\\{e_{ij}\otimes e_{jk}\otimes e_{ki}|1\leq i\leq
m,1\leq j\leq n,1\leq k\leq p\\}$ the _natural algorithm_ computing $\langle
m,n,p\rangle$.

Suppose that $\langle m,n,p\rangle=t_{1}+t_{2}+\cdots+t_{s}$, where
$t_{i}=u_{i}\otimes v_{i}\otimes w_{i}$ and $u_{i}\in\mathbb{C}^{m\times n}$,
$v_{i}\in\mathbb{C}^{n\times p}$, $w_{i}\in\mathbb{C}^{p\times m}$. Let
$V=\mathbb{C}^{m\times n}\otimes\mathbb{C}^{n\times
p}\otimes\mathbb{C}^{p\times m}$. For elements $a\in GL_{m}(\mathbb{C})$,
$b\in GL_{n}(\mathbb{C})$, $c\in GL_{p}(\mathbb{C})$ define transformation
$T(a,b,c):V\to V$ by the formula

$T(a,b,c)(x\otimes y\otimes z)=axb^{-1}\otimes byc^{-1}\otimes cza^{-1}.$

It was shown in Proposition 4.8 of [8] that $\Gamma^{0}(\langle m,n,p\rangle)$
consists of $T(a,b,c)$.

Recall that a _generalized permutation matrix_ is a matrix of the form $G=PD$,
in which $P,D\in\mathbb{C}^{n\times n}$, $P$ is a permutation matrix, and $D$
is a nonsingular diagonal matrix [19]. So $P=(\delta_{i,\pi(j)})$ for some
permutation $\pi\in S_{n}$, where $\delta$ is the Kronecker symbol. Denote the
set of generalised permutation matrices of order $n$ by $\mathcal{P}_{n}$.
Recall that $\mathcal{D}_{n}$ is the set of nonsigular diagonal matrices over
$\mathbb{C}$, which is a subgroup of $GL_{n}(\mathbb{C})$. By the definition
of $\mathcal{P}_{n}$ we have the following proposition.

######  Proposition 3.2.

$\mathcal{P}_{n}$ is isomorphic to the group $\mathcal{D}_{n}\rtimes S_{n}$.

In the following, if $V$ is a linear space and
$\\{v_{1},v_{2},...,v_{k}\\}\subseteq V$ be a subset (may be a multiset) of
vectors, the linear space spanned by $\\{v_{1},v_{2},...,v_{k}\\}$ is denoted
by $\langle v_{1},v_{2},...,v_{k}\rangle$.

######  Lemma 3.3.

Let $L=\\{\langle v_{1}\rangle,\langle v_{2}\rangle,...,\langle
v_{m}\rangle\\}\subseteq\mathbb{C}^{n}$ be a subset of one dimensional spaces
(lines) of $\mathbb{C}^{n}$. Let $\\{e_{i}|i=1,2,...,n\\}$ be the standard
basis of $\mathbb{C}^{n}$. Suppose that $\langle
v_{1},v_{2},...,v_{m}\rangle=\mathbb{C}^{n}$. Suppose that $A\in
GL_{n}(\mathbb{C})$ preserves $L$. Then there exists a $B\in
GL_{n}(\mathbb{C})$ and a $P_{A}\in\mathcal{P}_{n}$ such that
$A=BP_{A}B^{-1}$, where $B$ is independent with the choice of $A$. If
$\\{e_{i}|i=1,2,...,n\\}\subseteq\\{v_{1},v_{2},...,v_{m}\\}$, then we can
choose $B$ as the identity of $GL_{n}(\mathbb{C})$, so $A=P_{A}$ is a
generalised permutation matrix.

###### Proof.

By assumption we have $n\leq m$. Since the linear span of
$\\{v_{1},v_{2},...,v_{m}\\}$ is $\mathbb{C}^{n}$, it has a maximal linearly
independent subset $M$ which consists of $n$ vectors. Without loss of
generality, suppose that $M=\\{v_{1},v_{2},...,v_{n}\\}$.

Suppose that $A\in GL_{n}(\mathbb{C})$ preserves $L$. In particular, $A$
preserves the lines $\\{\langle v_{1}\rangle,\langle v_{2}\rangle,...,\langle
v_{n}\rangle\\}$. Let $\tilde{M}=(v_{1},v_{2},...,v_{n})\in\mathbb{C}^{n\times
n}$ be the matrix consists of $v_{i}$ ($i=1,2,...,n$). It implies that

$\tilde{A}\tilde{M}=(\lambda_{1}v_{1},\lambda_{2}v_{2},...,\lambda_{n}v_{n})P=\tilde{M}DP=\tilde{M}PD^{\prime},$

where $P$ is a permutation matrix,
$D=diag(\lambda_{1},\lambda_{2},...,\lambda_{n})$ and
$D^{\prime}=diag(\lambda_{i_{1}},\lambda_{i_{2}},...,\lambda_{i_{n}})$
($\lambda_{i_{j}}$ are obtained by some permutation of $\lambda_{i}$). Since
$v_{1},v_{2},...,v_{n}$ are linearly independent, $\tilde{M}$ is invertible.
Then we have

$A=\tilde{M}PD^{\prime}\tilde{M}^{-1}$ (3.4)

In (3.4), setting $\tilde{M}=B$ and $PD^{\prime}=P_{A}$, we have
$A=BP_{A}B^{-1}$. Moreover, we can see that $B$ is independent with the choice
of $A$. In particular, if
$\\{e_{i}|i=1,2,...,n\\}\subseteq\\{v_{1},v_{2},...,v_{m}\\}$, we can set
$B=(e_{1},e_{2},...,e_{n})$ which is the identity of $GL_{n}(\mathbb{C})$. ∎

######  Remark 3.4.

Let $L=\\{\langle v_{1}\rangle,\langle v_{2}\rangle,...,\langle
v_{m}\rangle\\}\subseteq\mathbb{C}^{n}$ be a subset of one dimensional spaces
(lines) of $\mathbb{C}^{n}$. Let

$P_{L}=\\{A\in GL_{n}(\mathbb{C})|~{}A~{}\text{preserves}~{}L\\}.$

So by Lemma 3.3, $P_{L}$ is the conjugate of a subgroup of $\mathcal{P}_{n}$.
Since the conjugate of a subgroup is isomorphic to itself, in the following,
we don’t distinguish them. So we also write $P_{L}\leq\mathcal{P}_{n}$.

Recall that on $\mathbb{C}^{m\times n}$ (similarly for $\mathbb{C}^{n\times
p}$ and $\mathbb{C}^{p\times m}$) there exists a natural inner product which
is defined by

$(a,b)=tr(ab^{*}),$

where $tr$ and ’*’ denote the trace and conjugate transpose, respectively.
With this inner product, $\mathbb{C}^{m\times n}$ becomes a Hilbert space.
Moreover, there is an induced inner product on $\mathbb{C}^{m\times
n}\otimes\mathbb{C}^{n\times p}\otimes\mathbb{C}^{p\times n}$, which makes it
into a Hilbert space too. Now we have the following lemma

######  Lemma 3.5.

Suppose that $\langle m,n,p\rangle=t_{1}+t_{2}+\cdots+t_{r}$. Let
$t_{i}=u_{i}\otimes v_{i}\otimes w_{i}$ ($i=1,2,...r$). Then $\langle
u_{1},u_{2},...,u_{r}\rangle=\mathbb{C}^{m\times n}$, $\langle
v_{1},v_{2},...,v_{r}\rangle=\mathbb{C}^{n\times p}$, $\langle
w_{1},w_{2},...,w_{r}\rangle=\mathbb{C}^{p\times m}$.

###### Proof.

It suffices to show $\langle u_{1},u_{2},...,u_{r}\rangle=\mathbb{C}^{m\times
n}$, the other two statements are similar.

If $\langle u_{1},u_{2},...,u_{r}\rangle\subsetneq\mathbb{C}^{m\times n}$ as a
proper linear subspace, there exists a matrix $0\neq a\in\mathbb{C}^{m\times
n}$ such that

$(a,u_{i})=tr(au_{i}^{*})=0,$

for $i=1,2,...,r$. Let $a=(a_{ij})$ and suppose that $a_{i_{0},j_{0}}\neq 0$
as an entry of $a$. Let $a\otimes e_{j_{0},k_{0}}\otimes
e_{k_{0},i_{0}}\in\mathbb{C}^{m\times n}\otimes\mathbb{C}^{n\times
p}\otimes\mathbb{C}^{p\times n}$, where $k_{0}\in\\{1,2,...,p\\}$ is a fixed
number. Then by assumption we have the following inner product equation

$(a\otimes e_{j_{0},k_{0}}\otimes e_{k_{0},i_{0}},\langle
m,n,p\rangle)=\left(a\otimes e_{j_{0},k_{0}}\otimes
e_{k_{0},i_{0}},\sum_{i=1}^{r}t_{i}\right).$ (3.5)

Since $\langle
m,n,p\rangle=\sum_{i=1}^{m}\sum_{j=1}^{n}\sum_{k=1}^{p}e_{ij}\otimes
e_{jk}\otimes e_{ki}$, with the induced inner product on $\mathbb{C}^{m\times
n}\otimes\mathbb{C}^{n\times p}\otimes\mathbb{C}^{p\times n}$, the left hand
side of (3.5) is equal to $a_{i_{0},j_{0}}\neq 0$. However, it is not hard to
see that the right hand side of (3.5) is 0, which is a contradiction. ∎

For $a=(a_{ij})\in\mathbb{C}^{m\times m}$ and $b\in\mathbb{C}^{n\times n}$, we
define the tensor product $a\otimes b\in\mathbb{C}^{mn\times mn}$ by

$a\otimes b=(a_{ij}b).$

Then by the definition of generalised permutation matrix, it is not hard to
obtain the following lemma.

######  Lemma 3.6.

If $a\in GL_{m}(\mathbb{C})$, $b\in GL_{n}(\mathbb{C})$ such that $a\otimes
b\in\mathcal{P}_{mn}$, then $a\in\mathcal{P}_{m}$ and $b\in\mathcal{P}_{n}$.
That is, both $a$ and $b$ are generalised permutation matrices.

For $x\in\mathbb{C}^{m\times n}$, define the _rowise vectorization map_
$\mathcal{R}:\mathbb{C}^{m\times n}\to\mathbb{C}^{mn\times 1}$ by
concatenating the rows of the matrix in $\mathbb{C}^{m\times n}$ as a column
vector of $\mathbb{C}^{mn\times 1}$. So $\mathcal{R}$ is a linear isomorphism.
For example, let $a=\left(\begin{array}[]{cc}a_{11}&a_{12}\\\ a_{21}&a_{22}\\\
\end{array}\right)\in\mathbb{C}^{2\times 2}$, then
$\mathcal{R}(a)=(a_{11},a_{12},a_{21},a_{22})^{t}\in\mathbb{C}^{4\times 1}$,
where $t$ is the transpose. For any linear map $\phi$ between
$\mathbb{C}^{m\times n}$, $\mathcal{R}$ induces a linear map $\tilde{\phi}$
between $\mathbb{C}^{mn\times 1}$ such that
$\mathcal{R}\circ\phi=\tilde{\phi}\circ\mathcal{R}$. In particular, if
$\phi(x)=uxv$ where $x\in\mathbb{C}^{m\times n}$, $u\in\mathbb{C}^{m\times m}$
and $v\in\mathbb{C}^{n\times n}$, then $\tilde{\phi}:\mathbb{C}^{mn\times
1}\to\mathbb{C}^{mn\times 1}$ is defined by

$\tilde{\phi}:y\mapsto(u\otimes v^{t})\left(y\right),$ (3.6)

for each $y=\mathcal{R}(x)\in\mathbb{C}^{mn\times 1}$.

Suppose that $\langle m,n,p\rangle=t_{1}+t_{2}+\cdots+t_{r}$ where
$t_{i}=u_{i}\otimes v_{i}\otimes w_{i}$. Then from Lemma 3.5 we have $\langle
u_{1},u_{2},...u_{r}\rangle=\mathbb{C}^{m\times n}$. So we can choose a
maximal linear independent subset
$\\{u_{i_{1}},u_{i_{2}},...u_{i_{mn}}\\}\subseteq\\{u_{1},u_{2},...u_{r}\\}$
such that the following matrix

$U_{mn}:=\left(\mathcal{R}(u_{i_{1}}),\mathcal{R}(u_{i_{2}}),\cdots\mathcal{R}(u_{i_{mn}})\right)\in\mathbb{C}^{mn\times
mn}$

is invertible, that is, $U_{mn}\in GL_{mn}(\mathbb{C})$. Similarly, we can
define $V_{np}\in GL_{np}(\mathbb{C})$ (resp. $W_{pm}\in GL_{pm}(\mathbb{C})$)
for some maximal linear independent subset of $\\{v_{1},v_{2},...v_{r}\\}$
(resp. $\\{w_{1},w_{2},...w_{r}\\}$). The set $\\{u_{1},u_{2},...u_{r}\\}$ is
said to have _D-property_ (Decomposable property) if for some maximal linear
independent subset
$\\{u_{i_{1}},u_{i_{2}},...u_{i_{mn}}\\}\subseteq\\{u_{1},u_{2},...u_{r}\\}$
we have $U_{mn}=U_{m}\otimes U_{n}$ for some $U_{m}\in GL_{m}(\mathbb{C})$ and
$U_{n}\in GL_{n}(\mathbb{C})$. Similarly, the set $\\{v_{1},v_{2},...v_{r}\\}$
(resp. $\\{w_{1},w_{2},...w_{r}\\}$) has _D-property_ if $V_{np}=V_{n}\otimes
V_{p}$ (resp. $W_{pm}=W_{p}\otimes W_{m}$) where $V_{n}\in GL_{n}(\mathbb{C})$
and $V_{p}\in GL_{p}(\mathbb{C})$ (resp. $W_{p}\in GL_{p}(\mathbb{C})$ and
$W_{m}\in GL_{m}(\mathbb{C})$).

######  Definition 3.7.

Given a tensor decomposition $\langle m,n,p\rangle=u_{1}\otimes v_{1}\otimes
w_{1}+u_{2}\otimes v_{2}\otimes w_{2}+\cdots u_{r}\otimes v_{r}\otimes w_{r}$.
Let $\mathcal{A}=\\{u_{i}\otimes v_{i}\otimes w_{i}|i=1,2,...,r\\}$ be the
corresponding algorithm computing $\langle m,n,p\rangle$. We call
$\mathcal{A}$ has _D-property_ if both $\\{u_{1},u_{2},...u_{r}\\}$,
$\\{v_{1},v_{2},...v_{r}\\}$ and $\\{w_{1},w_{2},...w_{r}\\}$ have
$D$-property.

The $D$-property defined above seems so special. However, we have some
examples.

######  Example 3.8.

It is not hard to see that the natural algorithm has $D$-property. Because
after a suitable change of the order of the maximal independent subset, we can
make $U_{mn}=I_{mn}=I_{m}\otimes I_{n}$, $V_{np}=I_{np}=I_{n}\otimes I_{p}$
and $W_{pm}=I_{pm}=I_{p}\otimes I_{m}$, where $I_{mn}$ is the identity of the
group $GL_{mn}(\mathbb{C})$ and similarly, for others. The Laderman algorithm
studied in Section 5 of [8] also has this property.

######  Theorem 3.9.

Let $\mathcal{A}=\\{u_{i}\otimes v_{i}\otimes w_{i}|i=1,2,...,r\\}$ be an
algorithm computing $\langle m,n,p\rangle$. If $\mathcal{A}$ has D-property,
then (with the convention in Remark 3.4)
$Aut(\mathcal{A})_{0}\leq\mathcal{P}_{m}\times\mathcal{P}_{n}\times\mathcal{P}_{p}$.

###### Proof.

By assumption, $Aut(\mathcal{A})_{0}=\\{T(a,b,c)\in\Gamma^{0}(\langle
m,n,p\rangle)|T(a,b,c)(\mathcal{A})=\mathcal{A}\\}$. So if $T(a,b,c)\in
Aut(\mathcal{A})_{0}$, then
$\mathcal{A}=\\{t_{i}|i=1,2,...,r\\}=\\{u_{i}\otimes v_{i}\otimes
w_{i}|i=1,2,...,r\\}=\\{au_{i}b^{-1}\otimes bv_{i}c^{-1}\otimes
cw_{i}a^{-1}|i=1,2,...,r\\}$.

By Lemma 5.9 of [8], we have $\varphi(x)=axb^{-1}$ (where
$x\in\mathbb{C}^{m\times n}$) is the linear map that preserves the set of
lines

$U=\\{\langle u_{i}\rangle|i=1,2,...,r\\},$

where $\langle u_{i}\rangle$ are the one dimensional spaces (lines) spanned by
$u_{i}$ in $\mathbb{C}^{m\times n}$. Let
$\mathcal{R}(x)\in\mathbb{C}^{mn\times 1}$ be the rowise vectorization of
$x\in\mathbb{C}^{m\times n}$. Let
$\tilde{\varphi}(y)=[a\otimes(b^{-1})^{t}](y)$ for $y\in\mathbb{C}^{mn\times
1}$ be the induced map defined in (3.6). Then we have $\varphi(x)=axb^{-1}$ if
and only if
$\tilde{\varphi}(\mathcal{R}(x))=[a\otimes(b^{-1})^{t}](\mathcal{R}(x))$. Let

$\tilde{U}=\\{\langle\mathcal{R}(u_{i})\rangle\subseteq\mathbb{C}^{mn\times
1}|i=1,2,...,r\\}.$

From Lemma 3.5, we have $\langle
u_{1},u_{2},...,u_{r}\rangle=\mathbb{C}^{m\times n}$. So
$\langle\mathcal{R}(u_{1}),\mathcal{R}(u_{2}),...,\mathcal{R}(u_{r})\rangle=\mathbb{C}^{mn\times
1}$. Then $\varphi$ preserves $U$ if and only if $\tilde{\varphi}$ preserves
$\tilde{U}$. So by Lemma 3.3, we have

$a\otimes(b^{-1})^{t}=U_{mn}P_{ab}U_{mn}^{-1},$

for some $U_{mn}\in GL_{mn}(\mathbb{C})$ and $P_{ab}\in\mathcal{P}_{mn}$.
Since $\\{u_{1},u_{2},...u_{r}\\}$ has $D$-property, we can set
$U_{mn}=U_{m}\otimes U_{n}$ for some $U_{m}\in GL_{m}(\mathbb{C})$ and
$U_{n}\in GL_{n}(\mathbb{C})$. So we have

$P_{ab}=\left(U_{m}^{-1}aU_{m}\right)\otimes\left(U_{n}^{-1}(b^{-1})^{t}U_{n}\right).$

Thus, by Lemma 3.6, we have

$U_{m}^{-1}aU_{m}=P_{a}\quad\text{and}\quad
U_{n}^{-1}(b^{-1})^{t}U_{n}=P_{b},$

for some $P_{a}\in\mathcal{P}_{m}$ and $P_{b}\in\mathcal{P}_{n}$. So
$a=U_{m}P_{a}U_{m}^{-1}\in U_{m}\mathcal{P}_{m}U_{m}^{-1}$ and
$b=(U_{n}^{t})^{-1}(P_{b}^{t})^{-1}U_{n}^{t}\in(U_{n}^{t})^{-1}\mathcal{P}_{n}U_{n}^{t}$.
Similar result holds for $c$.

So we have
$Aut(\mathcal{A})_{0}\leq\mathcal{P}_{m}\times\mathcal{P}_{n}\times\mathcal{P}_{p}$.
∎

Let $Q(m,n,p)$ be a subgroup of $\Gamma(\langle m,n,p\rangle)$, isomorphic to
$S_{3}$, $\mathbb{Z}_{2}$, or $1$, when $|\\{m,n,p\\}|$= 1, 2, or 3,
respectively. Just as in the proof of Theorem 4.12 and Lemma 5.8 of [8],
$Aut(\mathcal{A})$ is the semidirect product of $Aut(\mathcal{A})_{0}$ with a
subgroup of $Q(m,n,p)$. By Theorem 3.9, we have the following corollary.

######  Corollary 3.10.

Suppose that $\mathcal{A}$ is an algorithm computing $\langle m,n,p\rangle$.
If $\mathcal{A}$ has $D$-property, then
$Aut(\mathcal{A})\leq(\mathcal{P}_{m}\times\mathcal{P}_{n}\times\mathcal{P}_{p})\rtimes
Q(m,n,p)$.

For the natural algorithm, we have the following corollary.

######  Corollary 3.11.

$Aut(\mathcal{A}(m,n,p))=(\mathcal{P}_{m}\times\mathcal{P}_{n}\times\mathcal{P}_{p})\rtimes
Q(m,n,p)$.

###### Proof.

From Example 3.8, we know that $\mathcal{A}(m,n,p)$ has $D$-property. So from
Corollary 3.10, in the following we only need to check that
$(\mathcal{P}_{m}\times\mathcal{P}_{n}\times\mathcal{P}_{p})\rtimes Q(m,n,p)$
is contained in $Aut(\mathcal{A}(m,n,p))$.

Let $a=P_{1}D_{1}\in\mathcal{P}_{m}$ where $P_{1}=(\delta_{i,\pi(j)})$ is a
permutation matrix corresponding to the permutation $\pi\in S_{m}$ and
$D_{1}=diag(a_{1},a_{2},...,a_{m})$ is a nonsingular diagonal matrix with
$a_{i}\in\mathbb{C}\setminus\\{0\\}$. Similarly, let
$b=P_{2}D_{2}\in\mathcal{P}_{n}$ where $P_{2}=(\delta_{i,\sigma(j)})$,
$D_{2}=diag(b_{1},b_{2},...,b_{n})$ and $\sigma\in S_{n}$. Let
$c=P_{3}D_{3}\in\mathcal{P}_{p}$ where $P_{2}=(\delta_{i,\tau(j)})$,
$D_{3}=diag(c_{1},c_{2},...,c_{p})$ and $\tau\in S_{p}$.

Then we can see that

$\displaystyle T(a,b,c)(e_{ij}\otimes e_{jk}\otimes e_{ki})$
$\displaystyle=a_{i}\left(e_{\pi^{-1}(i),\sigma^{-1}(j)}\right)b_{j}^{-1}\otimes
b_{j}\left(e_{\sigma^{-1}(j),\tau^{-1}(k)}\right)c_{k}^{-1}\otimes
c_{k}\left(e_{\tau^{-1}(k),\pi^{-1}(i)}\right)a_{i}^{-1}$
$\displaystyle=e_{\pi^{-1}(i),\sigma^{-1}(j)}\otimes
e_{\sigma^{-1}(j),\tau^{-1}(k)}\otimes e_{\tau^{-1}(k),\pi^{-1}(i)}.$

Hence,

$\displaystyle T(a,b,c)\mathcal{A}(m,n,p)$
$\displaystyle=\\{e_{\pi^{-1}(i),\sigma^{-1}(j)}\otimes
e_{\sigma^{-1}(j),\tau^{-1}(k)}\otimes e_{\tau^{-1}(k),\pi^{-1}(i)}|1\leq
i\leq m,1\leq j\leq n,1\leq k\leq p\\}$ $\displaystyle=\\{e_{ij}\otimes
e_{jk}\otimes e_{ki}|1\leq i\leq m,1\leq j\leq n,1\leq k\leq p\\}$
$\displaystyle=\mathcal{A}(m,n,p).$

Thus, by Theorem 3.9 we have
$Aut(\mathcal{A}(m,n,p))_{0}=\mathcal{P}_{m}\times\mathcal{P}_{n}\times\mathcal{P}_{p}$.

Since $Aut(\mathcal{A}(m,n,p))$ is also preserved under the action of
$Q(m,n,p)$ (see e.g. Theorem 4.12 of [8]), we have
$(\mathcal{P}_{m}\times\mathcal{P}_{n}\times\mathcal{P}_{p})\rtimes
Q(m,n,p)\subseteq Aut(\mathcal{A}(m,n,p))$. ∎

######  Remark 3.12.

Conversely, it is interesting to show that if
$Aut(\mathcal{A})=(\mathcal{P}_{m}\times\mathcal{P}_{n}\times\mathcal{P}_{p})\rtimes
Q(m,n,p)$, then $\mathcal{A}$ should be the natural algorithm
$\mathcal{A}(m,n,p)$.

By the discussions in Section 4.3 of [8], we have the following proposition.

######  Proposition 3.13.

[8, Sect.4.3] $\Gamma^{0}(\langle m,n,p\rangle)=PGL_{m}(\mathbb{C})\times
PGL_{n}(\mathbb{C})\times PGL_{p}(\mathbb{C})$ and $\Gamma(\langle
m,n,p\rangle)=\Gamma^{0}(\langle m,n,p\rangle)\rtimes Q(m,n,p)$.

For a point $q\in V(m,n,p;r)$, by (3.2) and (3.3) there exists a tensor
decomposition of $\langle m,n,p\rangle$ of length $r$:

$\langle m,n,p\rangle=t^{q}_{1}+t^{q}_{2}+\cdots+t^{q}_{r},$ (3.7)

where $t^{q}_{i}=u_{i}^{q}\otimes v_{i}^{q}\otimes
w_{i}^{q}\in\mathbb{C}^{m\times n}\otimes\mathbb{C}^{n\times
p}\otimes\mathbb{C}^{p\times m}$.

######  Corollary 3.14.

For a point $q\in V(m,n,p;r)$, with notations in (3.7) let
$\mathcal{A}^{q}=\\{t^{q}_{1},t^{q}_{2},...,t^{q}_{r}\\}$ be the corresponding
algorithm of length $r$ computing $\langle m,n,p\rangle$. If $\mathcal{A}^{q}$
has D-property, then

$\dim_{q}V(m,n,p;r)\geq m^{2}+n^{2}+p^{2}-m-m-p-3.$

###### Proof.

Since $\mathcal{A}^{q}$ has D-property,
$\mathcal{A}^{q}\leq(\mathcal{P}_{m}\times\mathcal{P}_{n}\times\mathcal{P}_{p})\rtimes
Q(m,n,p)$ by Corollary 3.10. So by Proposition 2.5 and 3.2, we have

$\dim Aut(\mathcal{A}^{q})\leq m+n+p.$

By the analysis in Subsection 2.2, the isotropy group $\Gamma(\langle
m,n,p\rangle)$ induces a group action on $V(m,n,p;r)$. Let $\Gamma(\langle
m,n,p\rangle)\cdot q$ denote the group orbit of $q$, which is induced by the
action of $\Gamma(\langle m,n,p\rangle)$ on $V(m,n,p;r)$. Then by Proposition
2.5, 2.6 and 3.13, we have

$\displaystyle\dim_{q}V(m,n,p;r)$ $\displaystyle\geq\dim\left(\Gamma(\langle
m,n,p\rangle)\cdot q\right)$ $\displaystyle=\dim\left(\Gamma(\langle
m,n,p\rangle)\right)-\dim Aut(\mathcal{A}^{q})$ $\displaystyle\geq
m^{2}+n^{2}+p^{2}-3-(m+n+p).$

∎

The $D$-property is special. By current results on automorphism groups (see
e.g. [8], [9] and [26]), we believe the $D$-property in Corollary 3.10 is not
necessary. So we have the following conjecture for any algorithms of (any)
length $r$ computing $\langle m,n,p\rangle$, that is, $r$ can be less or more
than $mnp$.

######  Conjecture 1.

Suppose that $\mathcal{A}$ is an algorithm of any length $r$ computing
$\langle m,n,p\rangle$. Then

$Aut(\mathcal{A})\leq(\mathcal{P}_{m}\times\mathcal{P}_{n}\times\mathcal{P}_{p})\rtimes
Q(m,n,p).$

###  3.3. Radical ideal and rank of $J_{q}(B(m,n,p;r))$ as an invariant

Let $I(2,2,2;7)$ denote the set

$\\{f\in\mathbb{C}[x_{1},x_{2},...,x_{84}]|f(p)=0~{}\text{when}~{}p\in
V(2,2,2;7)\\}.$

It is the vanishing ideal of $V(2,2,2;7)$ which is radical. On the other hand,
let $\langle B(2,2,2;7)\rangle$ denote the ideal generated by the Brent
equations $B(2,2,2;7)$. We have that $\langle B(2,2,2;7)\rangle$ is strictly
contained in $I(2,2,2;7)$. The reason is as follows.

Suppose that $I(2,2,2;7)=\langle f_{1},f_{2},...,f_{k}\rangle$ where
$f_{i}\in\mathbb{C}[x_{1},x_{2},...,x_{84}]$. It was shown in [12] that the
isotropy group $\Gamma(\langle 2,2,2\rangle)$ acts transitively on
$V(2,2,2;7)$ and $\dim V(2,2,2;7)=9$. So by Proposition 2.4, $V(2,2,2;7)$ is a
smooth affine variety, which has no singular points. So we have $\dim
V(2,2,2;7)=84-rank~{}J_{p}(f_{1},f_{2},...,f_{k})$ for $p\in V(2,2,2;7)$.
Since the Brent equations $B(2,2,2;7)$ have 64 equations and 84 variables, the
rank of $J_{p}(B(2,2,2;7))$ can not exceed 64. So
$84-rank~{}J_{p}(B(2,2,2;7))\geq 20>9$. So we have $\langle
B(2,2,2;7)\rangle\subsetneq I(2,2,2;7)$. In fact, we calculated that
$rank~{}J_{p}(B(2,2,2;7))=61$ when $p$ is Strassen’s algorithm [29]. So the
ideal generated by Brent equations may not be radical.

Generally, let $k=(mn+np+pm)r$ and $I(m,n,p;r)$ denote the set

$\\{f\in\mathbb{C}[x_{1},x_{2},...,x_{k}]|f(p)=0~{}\text{when}~{}p\in
V(m,n,p;r)\\},$

that is, the vanishing ideal of $V(m,n,p;r)$. Let $\langle B(m,n,p;r)\rangle$
denote the ideal generated by the Brent equations $B(m,n,p;r)$. By the
discussions above, $\langle B(m,n,p;r)\rangle$ may not be equal to
$I(m,n,p;r)$. So from Corollary 2.8, we can see that
$rank~{}J_{q}(B(m,n,p;r))$ may not be equal to
$rank~{}J_{q^{\prime}}(B(m,n,p;r))$ when $q$ and $q^{\prime}$ lie in the same
group orbit under the action of $\Gamma(\langle m,n,p\rangle)$ on
$V(m,n,p;r)$. However, by random experiments in computer we have not found
counterexamples. So we have the following question

######  Question 3.15.

Does $rank~{}J_{q}(B(m,n,p;r))=rank~{}J_{q^{\prime}}(B(m,n,p;r))$ when $q$ and
$q^{\prime}$ lie in the same group orbit under the action of $\Gamma(\langle
m,n,p\rangle)$ on $V(m,n,p;r)$?

If the answer of Question 3.15 is affirmative, we get another criterion which
can be used to distinguish group orbits.

######  Remark 3.16.

Since the rank of $J_{q}(B(m,n,p;r))$ is finite and the number of group orbits
may be infinite [20], it has limitation when distinguishing group orbits just
by the rank of $J_{q}(B(m,n,p;r))$.

By now, some efficient algorithms and criterions are raised to distinguish
group orbits, such as [2, 18, 21] and the supplementary information of [15].
To distinguish the group orbits more efficiently, we should combine all these
methods.

## Acknowledgments

We are very grateful to the editors and referees for their valuable comments
and suggestions.

X. Li is supported by National Natural Science Foundation of China (Grant
No.11801506) and the National Science Basic Research Plan in Shaanxi Province
of China (2021JQ-661). Y. Bao is supported by the NSFC (Grant No. 11801117)
and the Natural Science Foundation of Guangdong Province. China (Grant No.
2018A030313268). L. Zhang is supported by the Zhejiang Provincial Natural
Science Foundation of China (Grant No. LY21A010015) and Grant 11601484, the
National Natural Science Foundation, People’s Republic of China.

## References

  * [1] Daniel J. Bates, Jonathan D. Hauenstein, C. Peterson, Andrew J. Sommese, A numerical local dimensions test for points on the solution set of a system of polynomial equations SIAM J. Numer. Anal. 47(2009), no.5, 3608-3623.
  * [2] Guillaume O. Berger, Pierre-Antoine Absil, Lieven De Lathauwer, R. M. Jungers, Marc Van Barel, Equivalent polyadic decompositions of matrix multiplication tensors. J. Comput. Appl. Math. 406(2022), Paper No. 113941, 17pp.
  * [3] P. Breiding, S. Kališnik, B. Sturmfels, M. Weinstein, Learning algebraic varieties from samples. Rev. Mat. Complut. 31(2018), no.3, 545-593.
  * [4] R. P. Brent, Algorithms for matrix multiplications, Comput. Sci. Dept. Report CS 157 (Stanford Univ. 1970).
  * [5] M. Brion, Introduction to actions of algebraic groups, Les cours du CIRM, 1 no.1: Hamiltonian Actions: invariants et classification, 2010.
  * [6] P. Bürgisser, M. Clausen, and M. Amin Shokrollahi. _Algebraic complexity theory_ , volume 315 of Grundlehren der Mathematischen Wissenschaften, Springer-Verlag, Berlin, 1997.
  * [7] Vladimir P. Burichenko, On symmetries of the strassen algorithm, arXiv:1408.6273, 2014.
  * [8] Vladimir P. Burichenko, Symmetries of matrix multiplication algorithms I, arXiv:1508.01110, 2015.
  * [9] Vladimir P. Burichenko, On automorphism group of a possible short algorithm for multiplication of $3\times 3$ matrices, arXiv:2211.06485, 2022.
  * [10] David A. Cox, J. Little, D. O’Shea, Ideals, varieties, and algorithms. Fourth edition. Undergraduate Texts in Mathematics. Springer, 2015.
  * [11] H.F. de Groote, On varieties of optimal algorithms for the computation of bilinear mappings. I. The isotropy group of a bilinear mapping, Theor. Comput. Sci. 7(1978), 1-24.
  * [12] H.F. de Groote, On varieties of optimal algorithms for the computation of bilinear mappings. II. Optimal algorithms for $2\times 2$ matrix multiplication, Theor. Comput. Sci. 7(1978), 127-148.
  * [13] H.F. de Groote, Lectures on the Complexity of Bilinear Problems, Springer-Verlag, 1987.
  * [14] W. Decker, F.O. Schreyer, Varieties, Gröbner Bases, and Algebraic Curves. To appear. 2007.
  * [15] A. Fawzi et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610:47-53, 2022.
  * [16] A. Fawzi et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Github: https://github.com/deepmind/alphatensor/, 2022.
  * [17] Marijn J. H. Heule, M. Kauers, M. Seidl, Matrix multiplication repository. http://www.algebra.uni-linz.ac.at/research/matrix-multiplication/. Accessed: 2019-04-26.
  * [18] Marijn J. H. Heule, M. Kauers, M. Seidl, New ways to multiply $3\times 3$-matrices, J. Symbolic Comput. 104(2021), 899-916.
  * [19] Roger A. Horn, Charles R. Johnson, Matrix analysis, Second edition. Cambridge University Press, Cambridge, 2013.
  * [20] Rodney W. Johnson, Aileen M. McLoughlin, Noncommutative bilinear algorithms for $3\times 3$ matrix multiplication. SIAM J. Comput. 15(1986), no.2, 595-603.
  * [21] M. Kauers, J. Moosbauer, A Normal Form for Matrix Multiplication Schemes. arXiv:2206.00550v1.
  * [22] J. M. Landsberg, Geometry and complexity theory. Cambridge Studies in Advanced Mathematics, 169. Cambridge University Press, Cambridge, 2017.
  * [23] P. Lairez, M. Safey El Din, Computing the dimension of real algebraic sets. ISSAC’21, 257-264, ACM, New York.
  * [24] Fiona Murnaghan, Linear algebraic groups. Harmonic analysis, the trace formula, and Shimura varieties, 379-391, Clay Math. Proc., 4, Amer. Math. Soc., Providence, RI, 2005.
  * [25] Joseph J. Rotman,  An introduction to the theory of groups. Fourth edition. Graduate Texts in Mathematics, 148. Springer-Verlag, New York, 1995.
  * [26] A. Sedoglavic. Fast matrix multiplication database [online]. Jan. 2023. http://fmm.univ-lille.fr/.
  * [27] A. V. Smirnov, The bilinear complexity and practical algorithms for matrix multiplication. Comput. Math. Math. Phys. 53(2013), no.12, 1781-1795.
  * [28] T. A. Springer, Linear algebraic groups. Second edition. Progress in Mathematics, 9. Birkhäuser Boston, Inc., Boston, MA, 1998.
  * [29] V. Strassen, Gaussian elimination is not optimal, Numer. Math. 13(1969), 354-356.