text:
\begin{document}

\title{On tensor rank and commuting matrices}

\author{Pascal Koiran\footnote{Univ Lyon, EnsL, UCBL, CNRS,  LIP, F-69342, LYON Cedex 07, France.
Email: {\tt pascal.koiran@ens-lyon.fr}.}}

\maketitle

\begin{abstract}
Obtaining superlinear lower bounds on tensor rank is a major open problem in complexity theory. In this paper we propose a generalization of the approach used by Strassen in the proof of his ${3 \over 2} n$
border rank lower bound.
Our approach revolves around a problem on  commuting matrices:

Given matrices $Z_1,\ldots,Z_p$ of size $n$ and an integer $r>n$, 	 are there commuting { diagonalizable} matrices $Z'_1,\ldots,Z'_p$
of size $r$ such that every $Z_k$ is embedded as a submatrix in the top-left corner of $Z'_k$?

As one of our main results, we show that this question always has a positive answer for $r \geq \rk(T)+n$, where $T$ denotes the tensor with slices $Z_1,\ldots,Z_p$.
Taking the contrapositive, if one can show for some specific matrices $Z_1,\ldots,Z_p$  and a specific integer~$r$ that this question has a negative answer, this yields the lower bound $\rk(T) > r-n$. There is a little bit of slack in the above $\rk(T)+n$
bound, but we also provide a number of {\em exact characterizations} of tensor rank and symmetric rank, for ordinary and symmetric tensors, over the fields of real and complex numbers.
Each of these characterizations points to a corresponding variation on the above approach.
In order to explain how Strassen's theorem fits within this framework we also provide a self-contained proof of his lower bound.
\end{abstract}

\section{Introduction}

The starting point of this paper is the celebrated lower bound on tensor rank by Strassen~\cite{strassen83}.
Before giving the statement of his theorem, we recall that a tensor of order 3 and format $m \times n \times p$ can be cut into $p$ "slices."
Each slice is a $m \times n$ matrix. These are the $z$-slices. One can of course cut $T$ in the two other directions into its $x$-slices
and $y$-slices.
\begin{theorem}[Strassen] \label{th:strassen}
Let $T$ be a complex tensor of format $n \times n \times 3$
with $z$-slices denoted  $A_1,A_2, A_3$.
If $A_1$ is invertible,
\begin{equation} \label{eq:strassen}
\rk(T) \geq n + \frac{1}{2} \rk(A_2A_1^{-1}A_3 - A_3A_1^{-1}A_2).
\end{equation}
\end{theorem}
We recall that obtaining rank lower bounds for tensors of order 3 is important because
this is an adequate complexity measure for
bilinear computations such as, e.g., matrix multiplication~\cite{Strassen73,BCS}. Moreover, strong enough lower bounds on the rank of (higher order) tensors would yield lower bounds on the size of arithmetic formulas~\cite{raz13}.

Clearly, one cannot hope to obtain more than a   ${3 \over 2} n$ lower bound  by a direct application of Theorem~\ref{th:strassen}. { This maximal lower bound is achieved for instance on the matrix multiplication tensor~\cite{strassen83}.}
Strassen showed that the right-hand side of (\ref{eq:strassen}) is in fact a lower bound on the border rank of $T$.
This is due to
the lower-semicontinuity of matrix rank (see \cite[Theorem 4.1]{strassen83} or the appendix  for details).
In the main body of the present paper we will only deal with tensor rank rather than border rank.
Theorem~\ref{th:strassen} proved important for several subsequent results. In particular, it was used by Bläser \cite{Blaser99} in the proof of his ${5 \over 2}n^2$ lower bound on the complexity of matrix multiplication.\footnote{This is still a linear lower bound since the relevant tensor for matrix multiplication is of format $n^2 \times n^2 \times n^2$.}
Generalizations of Theorem \ref{th:strassen} (in its border rank version)
were given by Landsberg and Manivel~\cite{landsberg08}.
For other approaches to rank lower bounds see e.g.~\cite{alexeev11} or the survey~\cite{blaser14}.

Today, almost 40 years after Strassen's result, we are still unable to prove superlinear lower bounds on tensor rank. In order to achieve this goal, one clearly needs to find a good way of taking into account more than 3 slices (like in Theorem \ref{th:strassen}), and more generally more than a constant number of slices (since the rank of such tensors is linearly bounded).
{ Results in this direction were obtained in a series of papers by Landsberg and his coauthors~\cite{landsberg08,landsberg13,landsberg15} (see~\cite{landsberg17} for the state of the art as of 2017).
 For instance, the "Koszul flattenings" of~\cite{landsberg15,landsbergGCT} yield lower bounds as high as  $(2p+1)n/(p+1)$ for tensors with $2p+1$ slices.
When $p >1$ this is a clear improvement on Theorem~\ref{th:strassen}, but the resulting lower bounds remain linear.
As we will explain in Section~\ref{sec:barriers}, there is a good reason for this state of affairs.}

In this paper we give several characterizations of tensor rank which point to a plausible approach to
the challenging task of improving on this state of the art, and ultimately of obtaining  superlinear lower bounds.
This approach revolves around variations on the following problem.
\begin{problem} \label{pb:commute}
Given matrices $Z_1,\ldots,Z_p$ of size $n$ and an integer $r>n$, 	 are there commuting matrices $Z'_1,\ldots,Z'_p$
of size $r$ such that $Z_k$ is a submatrix of $Z'_k$ for $k=1,\ldots,p$?
\end{problem}
Here and in the remainder of this paper, when we say that $Z_k$ is a submatrix of $Z'_k$ we mean that $Z_k$ appears in the top-left corner of $Z'_k$, i.e., $(Z'_k)_{ij} = (Z_k)_{ij}$ for $1 \leq i,j \leq n$. We will also say that $Z_1,\ldots,Z_k$ are {\em embedded as submatrices} in $Z'_1,\ldots,Z'_k$.
Theorem~\ref{th:strassen} fits naturally within this framework. Indeed, the quantity $\rk(A_2A_1^{-1}A_3 - A_3A_1^{-1}A_2)$
in that theorem can be seen as a measure of the lack of commutativity of the matrices $A_1^{-1}A_2$ and $A_1^{-1}A_3$
(this measure is equal to 0 iff the matrices commute).
In fact, as part of his proof of Theorem \ref{th:strassen}, Strassen offered a solution to Problem~\ref{pb:commute} for the case of two matrices (see Lemma~\ref{lem:strassen} in Section~\ref{sec:strassen}).
{ This approach cannot be pushed much further because Problem~\ref{pb:commute} always has a positive solution
for $r=2n$. We can indeed take:
\begin{equation} \label{eq:2n}
Z'_i = \begin{pmatrix}
Z_i & -Z_i\\
Z_i & -Z_i
\end{pmatrix}
\end{equation}
Since $Z'_i Z'_j=0$ for all $i,j$. For this reason, we will focus on a variation of Problem~\ref{pb:commute} with the additional
requirement that the $Z'_i$ all be diagonalizable. It turns out that for any tuple of matrices, there is  still a positive solution when
$r$ is large enough.}
Indeed, as one of our main results we provide the following bound.
\begin{theorem} \label{th:embedding}
Let $(A_1,\ldots,A_p)$ be a tuple of $p$ arbitrary matrices of $M_n(K)$. These matrices can be embedded as submatrices in a commuting tuple of
$p$ diagonalizable matrices of size $\rk(T)+n$, where $T$ denotes the tensor with slices $A_1,\ldots,A_p$.
\end{theorem}
In the above theorem and in the remainder of the paper, $K$ denotes a subfield of the field of complex numbers.
Theorem~\ref{th:embedding} points to the following approach toward lower bounds: if we can show for some specific matrices $Z_1,\ldots,Z_p$  and a specific integer~$r$ that Problem~\ref{pb:commute} has a negative answer, we have obtained the lower bound $\rk(T) > r-n$ where $T$ denotes the tensor with slices $A_1,\ldots,A_p$.
For any matrix tuple, the bound $\rk(T)+n$ is optimal up to the additive term $n$ (see Theorem~\ref{th:tight} in Section~\ref{sec:commuteagain}). As a result, proving a superlinear lower bound on tensor rank is { equivalent}
to proving  a superlinear lower bound on the smallest $r$ for which Problem~\ref{pb:commute} can be solved with
matrices $Z'_k$ that are all diagonalizable.

This paper provides several variations on Theorem \ref{th:embedding} which point to corresponding variations on this "commutation approach."
For instance, as explained in Section~\ref{sec:results},
we can restrict our search to matrices $Z'_k$ that are symmetric if we seek
lower bounds on the symmetric rank of symmetric tensors.
{ Besides Strassen's work~\cite{strassen83}, we will see that some elements of the commutation approach can already be found in~\cite{griesser86,landsbergGCT}. More information on the history of lower bounds for tensor rank and border rank
can be found in~\cite{landsbergTensors,landsbergGCT,ottaviani07}.}

\subsection{Results and methods} \label{sec:results}

There is a little bit of slack in Theorem \ref{th:embedding}: the smallest integer for which the embedding is possible lies in the interval $[\rk(T), \rk(T)+n]$. In addition to this result, we provide {\em exact characterizations} of tensor rank in various scenarios. For instance, we give at the end of Section~\ref{sec:rortho} the following characterization of symmetric rank for real symmetric tensors. The symmetric rank, denoted $\sk(T)$ in this paper, is a natural complexity measure for symmetric tensors which satisfies $\rk(T) \leq \sk(T) \leq 4\rk(T)$.
See Section~\ref{sec:background} for background on tensor rank and symmetric rank.
\begin{theorem} \label{th:srealintro}
Let $T$ be a real symmetric tensor of order 3 and size $n$. For any integer~$r$, $\sk(T) \leq r$ if and only if there is  a real symmetric tensor $S$ of order 3 and size $r+n$
such that:
\begin{itemize}
\item[(i)] The slices of $S$ commute.
\item[(ii)] $T$ is a subtensor of $S$ in the sense that $T_{ijk} = S_{ijk}$ for all $1 \leq i,j,k \leq n$.
\item[(iii)] Any matrix in the subspace spanned by the slices of $S$ is of rank at most~$r$.
\end{itemize}
\end{theorem}
As another example, returning to ordinary tensors we give the following characterization of tensor rank in Section~\ref{subsec:oind}.
\begin{theorem} \label{th:indintro}
Let $T$ be a tensor
of format $n \times n \times p$ over $K$.
Assume moreover that the span of the  $z$-slices of $T$
 contains an invertible matrix.
For any integer $r \geq n$, $\rk(T) \leq r$ if and only if there is  a  tensor $S \in K^{r \times r \times p}$ with  $z$-slices $Z_1,\ldots,Z_p$
such that:
\begin{itemize}
\item[(i)] The span of $Z_1,\ldots,Z_p$
contains an invertible matrix.
\item[(ii)]   For any invertible matrix $Z$ in the span of $Z_1,\ldots,Z_p$, the matrices  $Z^{-1}Z_i$ commute and are diagonalizable over $K$.
\item[(iii)] $T$ is a subtensor of $S$ in the sense that $T_{ijk} = S_{ijk}$ for  $1 \leq i,j \leq n$ and $1 \leq k \leq p$.
\end{itemize}
\end{theorem}
Note that the commutativity condition on the matrices $Z^{-1}Z_i$ in the above theorem  is reminiscent of Strassen's Theorem.
As we will see, Theorem~\ref{th:indintro} is an important step toward the proof of Theorem~\ref{th:embedding}.
In a nutshell, to prove the latter theorem we manage to apply Theorem \ref{th:indintro} with $Z$ equal to the identity matrix.
{ This result appears as Proposition~5.1.4.1 in~\cite{landsbergGCT} under the additional assumptions: $K=\cc$, $n=p=r$ and $T$ is "concise" in the sense of \cite[Definition~2.1.7.3]{landsbergGCT}.}

A word is in order regarding the proofs of Theorem \ref{th:srealintro}, Theorem \ref{th:indintro} and of the other exact characterizations is this paper. They are all based on "simple characterizations" of tensor decompositions of a restricted
form. For instance, Theorem \ref{th:srealintro} relies on a characterization of symmetric orthogonal decompositions,
which are of the form
\begin{equation} \label{eq:symdecomp}
T = \sum_{i=1}^r v_i^{\otimes 3}
\end{equation}
where the $v_i$ are nonzero pairwise orthogonal vectors. Not all symmetric tensors admit such a decomposition,
but those that do admit a very simple characterization: their slices must commute~\cite{boralevi17,koiran2019ortho}.
In general, one cannot expect such a simple characterization for tensor rank or symmetric rank since computing these
quantities  is NP-hard~\cite{hastad90,schaefer16,shitov16}.
An arbitrary symmetric decomposition is of the form (\ref{eq:symdecomp}), with the orthogonality constraint on the~$v_i$ removed. From an arbitrary family $v_1,\ldots,v_r$ of vectors of $\rr^n$ we can obtain an orthogonal family in $\rr^{r+n}$
by adding $r$ coordinates to each vector (Section~\ref{sec:rortho}, Lemma~\ref{lem:extension}). In this way we obtain an orthogonal
decomposition of a symmetric tensor of size $r+n$, and a way to transform the characterization of symmetric orthogonal
decompositions into a characterization of arbitrary symmetric decompositions.
The proofs of our other results follow a similar pattern. In particular, we give in Section \ref{sec:ind} an alternative
characterization of the symmetric rank of real symmetric tensors.
The role of orthogonal decompositions is now played  by {\em independent decompositions}, i.e., instead of an orthogonality
requirement on the $v_i$ we only assume that they are linearly independent.\footnote{ Joseph Landsberg (personal communication) has pointed out that Griesser used a similar method
in the proof of his border rank lower bound (\cite{griesser86} and~\cite[Theorem~5.2.2.1]{landsbergGCT}).}
This leads to a total of 8 different scenarios: we consider symmetric and ordinary tensors, over the fields of real and complex numbers,
and we characterize their ranks using orthogonal or independent decompositions. For independent decompositions we can handle
all subfields of $\cc$ in a single theorem (like in Theorem~\ref{th:indintro}). We therefore need to  present only 6 exact characterizations of rank and symmetric rank. Toward the proof of Theorem~\ref{th:indintro} we need a "simple characterization" of independent decompositions of ordinary tensors.
 We propose such a characterization in Theorem \ref{th:indordi} since we could not find a suitable one in the literature.
Tensor decomposition algorithms based on similar linear independence assumptions have been proposed for instance in~\cite{lathauwer06,lathauwer04}.
The characterization in Theorem~\ref{th:indordi} seems especially related to Jennrich's algorithm (see~\cite{moitra18} and the references therein).

{\subsection{Connection to barrier results} \label{sec:barriers}

Many lower bounds in algebraic complexity are obtained by estimating the rank of a matrix $L(f)$ associated to a polynomial $f$, or to a tensor. In order to obtain a lower bound for a "hard polynomial" $\hat{f}$ one must show that $\rk L(\hat{f})$ is "large", and
that  "small" arithmetic circuits can only compute polynomials $f$ for which $\rk L(f)$ is small.
Very often, the map $f \mapsto L(f)$ is linear. In this case we have a {\em rank method} in the sense of~\cite{efremenko18}.
It is shown in that paper that rank methods face severe limitations. For instance, they cannot prove lower bounds larger than
$8n$ on the rank of order 3 tensors.
An extensive list of lower bound methods belonging to this category can be found in~\cite{efremenko18}.
It includes for instance the methods of partial derivatives~\cite{NW96}  and shifted partial derivatives~(\cite{GKKS14,fournier15lower} among others).
Strassen's theorem, however, is conspicuously absent from their list and indeed, the proofs of Theorem~\ref{th:strassen} in~\cite{strassen83} or in the present paper follow a very different pattern. It is nevertheless possible to prove a certain version
of Theorem~\ref{th:strassen} by a rank method: see Theorem~\ref{th:rank} in the appendix.

In its full generality, the "commutation approach" proposed in the present paper is immune to the barrier result from~\cite{efremenko18}
for a very simple reason: as explained after the statement of Theorem~\ref{th:embedding}, proving a lower bound
on tensor rank (by any approach) is equivalent up to a small additive term to proving a lower bound by the commutation approach.
At this stage, the missing ingredient is a good way of giving a negative answer to Problem~\ref{pb:commute}
or to the similar problems arising from the characterizations of tensor rank and symmetric rank appearing in Sections~3 to~6.
This was arguably the easier part of the proof of Strassen's theorem (see Lemma~\ref{lem:strassen} in Section~\ref{sec:strassen}), but obtaining a superlinear lower bound is
likely to be much harder.

\subsection{Organization of the paper}

We begin in Section~\ref{sec:background} with some background on the decomposition of ordinary and symmetric tensors.
We also provide an outline of the proof of Strassen's theorem
so the reader can better appreciate its relations to Problem~\ref{pb:commute} and Theorem~\ref{th:indintro}.
The main results of the paper appear in Sections~3 to~6. They are organized according to the different scenarios presented in
Section~\ref{sec:results}:  we consider symmetric and ordinary tensors,
and we characterize their ranks using orthogonal or independent decompositions.
The four resulting sections are further divided when necessary into a real and a complex case.
In particular, Theorem~\ref{th:srealintro} is proved in Section~\ref{sec:rortho}, Theorem~\ref{th:indintro} is proved in Section~\ref{subsec:oind} and Theorem~\ref{th:embedding} in Section~\ref{sec:commuteagain}.
In the appendix we complete the proof of Theorem~\ref{th:strassen} and of its border rank version. We also point out some differences with Strassen's original proof, and we give a variation on Theorem~\ref{th:strassen} which can be proved
by a rank method in the sense of~\cite{efremenko18}.

\section{Background on tensor rank} \label{sec:background}

Recall that a tensor can be viewed as a multidimensional array with entries in some field $K$.
The main cases of interest for this paper are $K=\rr$ and $K=\cc$. We will only consider tensors of order 3, i.e., elements of $K^{m \times n \times p}$.
We will sometimes work with square tensors, for which $m=n=p$.
We denote by $M_{n,p}(K)$ the set of matrices with $n$ rows, $p$ columns and entries in~$K$.
We denote by $M_n(K)$ the set of square matrices of size $n$, by~$GL_n(K)$ the group of invertible matrices of size $n$,
and by $I_n$ the identity matrix of size $n$.

Given 3 vectors $u \in K^m, v \in K^n, w \in K^p$ we recall that their tensor product $u \otimes v \otimes w$ is the tensor of  format $m \times n \times p$
with entries: $T_{ijk}=u_i  v_j w_k$.
By definition, a tensor of this form with $u,v,w \neq 0$ is said to be of {\em rank one}.
The rank of an arbitrary tensor $T$ is defined as the smallest integer $r$ such that $T$ can be written as a sum of $r$ tensors of rank one (and the rank of $T=0$ is 0).
An elementary counting of the number of independent parameters in such a decomposition shows that most of the square tensors of size $n$ must be of rank $\Omega(n^2)$.  For $K = \cc$, the value of the generic rank
is known exactly: it is equal to 5 for $n=3$~\cite{strassen83} and to $\lceil n^3/(3n-2) \rceil$ for $n \neq 3$~\cite{lickteig85}. The same paper also gives a simple formula
for the dimension of the set of tensors of rank at most~$r$.
For tensors of order 4 or more, the exact value of the generic rank is not known in general. The existing  results are summarized in~\cite[section~5.5]{landsbergTensors}.

By cutting a tensor $T \in K^{m \times n \times p}$ into its $p$ slices in the $z$ direction we obtain $m \times n$ matrices (the so-called "$z$-slices"). This will allow us to study the properties of $T$ with tools from linear algebra. It is therefore  important
to know what the slices of a tensor look like given a decomposition
\begin{equation} \label{eq:decomp}
T=\sum_{i=1}^r u_i \otimes v_i \otimes w_i
\end{equation}
as a sum of rank-1 tensors.
First, we note that the $k$-th $z$-slice of $ u_i \otimes v_i \otimes w_i$ is the rank-one matrix $w_{ik} (u_i v_i^T)$.
As a result, the $k$-th $z$-slice of $T$ is
$$Z_k=\sum_{i=1}^r w_{ik} (u_i v_i^T).$$
This can be written in more compact notation:
\begin{equation} \label{eq:slices}
Z_k  = U^T D_k V
\end{equation}
where $U$ is the matrix with the $u_i$ as row vectors, $V$ is the matrix with the $v_i$ as row vectors and $D_k$ is the diagonal matrix
$\diag(w_{1k},\ldots,w_{rk})$. We record this observation in the following proposition.
\begin{proposition} \label{prop:slices}
For a tensor $T$ of format $m \times n \times p$ we have $\rk(T) \leq r$ iff there are diagonal matrices $D_1,\ldots,D_p$ of size $r$ and two matrices $U \in M_{r,m}(K)$, $V \in M_{r,n}(K)$ such that the $z$-slices of $T$ satisfy $Z_k  = U^T D_k V$ for $k=1,\ldots,p$.
 In this case, we have a decomposition of $T$ as in~(\ref{eq:decomp}) where the $u_i$ are the rows of $U$, the $v_i$ are the rows of $V$ and
$D_k = \diag(w_{1k},\ldots,w_{rk})$, i.e., the $k$-th coordinate of~$w_i$ is the $i$-th diagonal entry of $D_k$.
\end{proposition}

A  tensor can be naturally interpreted as the array of coefficients of the trilinear form in $m+n+p$ variables:
\begin{equation} \label{eq:multilinear}
t(x_1,\ldots,x_m,y_1,\ldots,y_n,z_1,\ldots,z_p)=\sum_{i,j,k} T_{ijk}x_iy_jz_k.
\end{equation}
For a decomposition of $T$ as in~(\ref{eq:decomp}) we have for the corresponding  trilinear form the decomposition:
\begin{equation} \label{eq:setmulti}
t(x,y,z)=\sum_{i=1}^r (u_i^Tx)(v_i^Ty) (w_i^Tz).
\end{equation}
Such an expression is sometimes called a "set-multilinear depth-3 homogeneous arithmetic circuit"~\cite{NW96,raz13}.

\subsection{Symmetric tensors}

A square tensor $T$ is said to be symmetric if $T_{ijk}$ is invariant under all 6 permutations of the indices $i,j,k$.
A symmetric tensor can be interpreted as the array of coefficients of the homogeneous polynomial
$$t'(x_1,\ldots,x_n)=\sum_{i,j,k=1}^n T_{ijk}x_ix_jx_k.$$
The relation with the multilinear form in (\ref{eq:multilinear}) is that $t'(x)=t(x,x,x)$.
For symmetric tensors one may consider arbitrary decompositions as in (\ref{eq:decomp}), but it is very natural to look for
 {\em symmetric decompositions } where $u_i=v_i=w_i$. Such a decomposition provides a decomposition
 $t'(x)=\sum_{i=1}^r (u_i^T x)^3$ as a sum of cubes of linear forms.
 The {\em symmetric rank}, denoted $\sk(T)$ in this paper,  is the smallest number of terms $r$ in any symmetric decomposition of~$T$.
 By definition we have $\sk(T) \geq \rk(T)$ for any symmetric tensor~$T$ (it was shown only recently that this inequality can be strict~\cite{shitov18}).
 In the other direction we have $\sk(T) \leq 4\rk(T)$.
 This can be shown by substituting $x=y=z$ in~(\ref{eq:setmulti}) and rewriting each of the $r$ products of linear forms as a sum of 4 cubes using the formula:\footnote{This can be generalized to tensors of any order $d$ using Fischer's formula \cite{fischer94}: we have $\sk(T) \leq 2^{d-1}\rk(T)$.}
 $$24uvw=(u+v+w)^3-(u-v+w)^3-(u+v-w)^3+(u-v-w)^3.$$

  In contrast to the ordinary case,  the exact value of the  symmetric rank for a generic symmetric tensor of any size and any order is known thanks to the Alexander-Hirschowitz theorem~\cite{alexander95,brambilla08}.

\subsection{Outline of the proof of Strassen's theorem} \label{sec:strassen}

In this section we provide an outline of the proof of Theorem~\ref{th:strassen} so the reader can better appreciate its relations to Problem~\ref{pb:commute} and Theorem~\ref{th:indintro}.
The first step of the proof is a reduction to the case where the first slice $A_1$ is the identity matrix. This is possible because multiplying each slice by $A_1^{-1}$ (or by any invertible matrix) does not change the tensor rank, as can be seen from Proposition~\ref{prop:slices}. Assuming that $A_1=I_n$, it therefore remains to show that:
$$r=\rk(T) \geq n + \frac{1}{2} \rk(A_2A_3 - A_3A_2).$$
The next step of the proof is akin to Theorem~\ref{th:indintro}: Strassen embeds $T$ in a tensor $S$ of format $r \times r \times 3$
having $I_r$ as its first slice (of course, this would be impossible without the assumption $A_1=I_n$).
As a result, we can take $Z=Z_1=I_r$ in Theorem~\ref{th:indintro}.(ii) and we conclude that the last two slices of $S$ commute.
More details on this step can be found in the appendix.

The final result therefore follows from the next lemma, which is Strassen's solution to Problem~\ref{pb:commute} for two matrices:
\begin{lemma} \label{lem:strassen}
If $A_2,A_3 \in M_n(K)$ can be embedded as submatrices in two commuting  matrices $A'_2,A'_3 \in M_r(K)$ we must have
$$r \geq n + \frac{1}{2} \rk(A_2A_3 - A_3A_2).$$
\end{lemma}
\begin{proof}
Consider the block decomposition of $A'_2$ and $A'_3$:
$$A'_i=
\begin{pmatrix}
A_i & B_i \\
C_i & D_i
\end{pmatrix}.$$
Since $A'_2$ and $A'_3$ commute we have $A_2A_3-A_3A_2 = B_3C_2-B_2C_3$.
Since $B_2$ and $B_3$ have only $r-n$ columns, $\rk(B_3C_2-B_2C_3) \leq 2(r-n)$.
\end{proof}

{This lemma can prove lower bounds on the size of the embedding up to $r=3n/2$. As explained in the introduction,
for $r=2n$ an embedding in commuting matrices is always possible. For the case of two matrices $A_2,A_3 \in M_n(K)$ considered in Lemma~\ref{lem:strassen}  one may also take:
$$A'_2 =  \begin{pmatrix}
A_2 & A_3\\
A_3 & A_2
\end{pmatrix},\
A'_3=  \begin{pmatrix}
A_3 & A_2\\
A_2 & A_3
\end{pmatrix},$$
as an alternative to~(\ref{eq:2n}).}

\section{Symmetric tensors: from orthogonal decompositions
to arbitrary decompositions} \label{sec:ortho}

In this section we give a proof of Theorem \ref{th:srealintro} and of its complex counterpart (Theorem~\ref{th:scomplexfinal}). As explained in Section~\ref{sec:results}, these results rely on the existence of "simple characterizations" for orthogonal tensor decompositions.

\subsection{Real tensors} \label{sec:rortho}

Following~\cite{boralevi17}, a real symmetric tensor of order $d$ and size $n$ is said to be {\em symmetrically odeco}
if one can write
\begin{equation} \label{eq:sodeco}
T = \sum_{i=1}^k \alpha_i v_i^{\otimes d}
\end{equation}
where $\alpha_i = \pm 1$ and
$v_1,\ldots,v_k$ are nonzero, pairwise orthogonal vectors in~$\rr^n$.
One may clearly take $\alpha_i=1$ for all $i$ when $d$ is an odd number.
\begin{theorem} \label{th:sodeco}
A real symmetric tensor of order 3 is symmetrically odeco if and only if its slices pairwise commute.
\end{theorem}
This result was first established in \cite{boralevi17} in a different language: instead of commuting slices, they give a characterization based on the associativity of a bilinear map associated to the tensor. The equivalent formulation in Theorem \ref{th:sodeco} is from \cite{koiran2019ortho}.

\begin{theorem} \label{th:sreal}
Let $T$ be a real symmetric tensor of order 3 and size $n$. For any integer $r$, $\sk(T) \leq r$ if and only if there is  a real symmetric tensor $S$ of order 3 and size $r+n$
such that:
\begin{itemize}
\item[(i)] The slices of $S$ commute.
\item[(ii)] $T$ is a subtensor of $S$ in the sense that $T_{ijk} = S_{ijk}$ for all $1 \leq i,j,k \leq n$.
\item[(iii)] $\sk(S) \leq r$.
\end{itemize}
\end{theorem}
The following lemma is needed for the proof of Theorem \ref{th:sreal}.
\begin{lemma} \label{lem:extension}
Let $u_1,\ldots,u_r$ be an arbitrary family of vectors in $\rr^n$. There exists a family $v_1,\ldots,v_r$ of pairwise orthogonal vectors of
$\rr^{r+n}$ such that $u_i$ is the orthogonal projection of $v_i$ on its first $n$ coordinates, i.e., $u_i=(v_{i1},\ldots,v_{in})$.
\end{lemma}
\begin{proof}
We are looking for a family $w_1,\ldots,w_r$ of vectors of $\rr^{r}$ such that $\langle u_i,u_j \rangle + \langle w_i,w_j \rangle = 0$ for $i \neq j$ since we can then use the coordinates of $w_i$ as the last $r$ coordinates of $v_i$. Let $A \in M_r(\rr)$ be the symmetric matrix
with entries $A_{ij}=-\langle u_i,u_j \rangle$ .
Fix a large enough constant $\lambda$ such that $B=A+\lambda I_r$ is positive semidefinite. This matrix must admit a Cholesky decomposition $B=LL^T$ and we can take the rows of $L$ as our vectors $w_i$.
\end{proof}
\begin{proof}[Proof of Theorem \ref{th:sreal}]
Suppose that properties (ii) and (iii) hold for $S$.
By~(iii), there are vectors $v_1,\ldots,v_r \in {\rr}^{n+r}$ such that $S=\sum_{i=1}^r v_i^{\otimes 3}$.
By~(ii), $\sk(T) \leq r$ since $T=\sum_{i=1}^r u_i^{\otimes 3}$ where $u_i$ is obtained from the first $n$ coordinates of $v_i$:
$u_i=(v_{i1},\ldots,v_{in})$.  Note that this argument does not use~(i).

For the converse, assume that $\sk(T) \leq r$, and let $$T=\sum_{i=1}^r u_i^{\otimes 3}$$ be a corresponding decomposition. Let $S=\sum_{i=1}^r v_i^{\otimes 3}$ where the orthogonal vectors $v_i$ are given by Lemma \ref{lem:extension}. Condition (ii) holds by construction of the $v_i$, and~(i) holds by Theorem \ref{th:sodeco}. Condition (iii) holds as well since $S$ is defined as a sum of $r$ tensors of rank at most 1.
\end{proof}

\begin{remark}
By Theorem \ref{th:sodeco}, a tensor $S$ satisfying only property (i) of Theorem \ref{th:sreal} will already satisfy $\sk(S)  \leq n+r$.

\end{remark}
The characterization in Theorem \ref{th:sreal} is not completely satisfactory because condition (iii) still appeals to the notion of symmetric rank. We would like instead a characterization in terms of properties of the slices only. For this we need two  additional facts.
\begin{lemma} \label{lem:rankr}
Let $K$ be an arbitrary field. Let $(u_1,\ldots,u_r)$ and $(v_1,\ldots, v_r)$ be two families of  vectors of $K^n$, respectively of rank $r_u$ and $r_v$.
For the  matrix $M=\sum_{i=1}^r  u_i v_i^T$ we have $\rk M \leq \min(r_u,r_v)$. Moreover, if $r_u=r_v=r$ then $\rk M = r$ as well.
\end{lemma}
\begin{proof}
In the expression for $M$ we can rewrite each $u_i$ as a linear combination of the elements of a basis $e_1,\ldots,e_{r_u}$.
This yields an expression for $M$ as a sum of $r_u$ matrices of rank at most 1, namely,
$$M=\sum_{i=1}^{r_u}  e_i w_i^T$$
where the $w_i$ are linear combinations of the $v_i$.
 Hence $\rk M \leq r_u$, and $\rk M \leq r_v$ by a similar argument.

Assume now that $r_u=r_v=r$. It remains to show that $\rk M = r$. This is equivalent to $\dim \ker M = n-r$.
A vector $x \in K^n$ is in the kernel
 if and only if $\sum_{i=1}^{r} (v_i^T x) u_i =0$. Since the $u_i$ are linearly independent, this is equivalent
 to $v_i^T x =0$ for all $i$. Using now the linear independence of the $v_i$, it follows that the solution space is of dimension $n-r$ as needed.
\end{proof}

For application in sections \ref{sec:oortho} and \ref{sec:oind}, the next proposition is stated for ordinary tensors.
In sections \ref{sec:ortho} and \ref{sec:ind} we only need to apply it to symmetric decompositions, namely, to the case $n=p$ and $u_i=v_i=w_i$.
\begin{proposition} \label{prop:span}
Let $K$ be an arbitrary field and let  $(u_1,\ldots,u_r)$, $(v_1,\ldots, v_r)$ be 2 families of  vectors of $K^n$, respectively of rank $r_u$ and $r_v$. Let  $(w_1,\ldots,w_r)$ be a family  of vectors of $K^p$ of rank $r_w$.
From these families, let us  construct the tensor $T=\sum_{i=1}^r u_i  \otimes v_i \otimes w_i$.
The rank of any matrix in the subspace spanned by the $z$-slices of $T$ is at most equal to $\min(r_u,r_v)$. Moreover,  if $r_u=r_v=r_w=r$ then
there is a matrix of rank $r$ in this subspace.
\end{proposition}
\begin{proof}
Let $Z_1,\ldots,Z_p$ be the $z$-slices of $T$.
We have already pointed out before (\ref{eq:slices}) that the $k$-th $z$-slice of $ u_i \otimes v_i \otimes w_i$ is $w_{ik} (u_i v_i^T)$.
As a result any matrix $M$ in the span of $Z_1,\ldots,Z_p$ is a linear combination
of the matrices $u_i v_i^T$.  It follows from  Lemma \ref{lem:rankr} or directly from~(\ref{eq:slices})  that $\rk M \leq \min(r_u,r_v)$.

Assume now that $r_u=r_v=r_w$
and consider a linear combination of slices
$$M=\sum_{k=1}^p x_k Z_k = \sum_{i=1}^r \sum_{k=1}^p w_{ik} x_k (u_i v_i^T).$$
Note that the coefficients of the matrices $u_i v_i^T$ in this expression are the entries of the matrix-vector product $W.x$, where $W$ is the matrix with the $w_i$ as rows. Since $W$ is of full row rank, one can obtain any desired values for these~$r$ coefficients by an appropriate choice of $x$.
If we choose $r$ nonzero values for these coefficients, it follows from Lemma \ref{lem:rankr} that the corresponding~$M$ is of rank $r$.
\end{proof}

As our final characterization of symmetric rank for real tensors, we can now give a proof of Theorem \ref{th:srealintro}.
For the reader's convenience we reproduce its statement below.
\begin{theorem} \label{th:srealfinal}
Let $T$ be a real symmetric tensor of order 3 and size $n$. For any integer~$r$, $\sk(T) \leq r$ if and only if there is  a real symmetric tensor $S$ of order 3 and size $r+n$
such that:
\begin{itemize}
\item[(i)] The slices of $S$ commute.
\item[(ii)] $T$ is a subtensor of $S$ in the sense that $T_{ijk} = S_{ijk}$ for all $1 \leq i,j,k \leq n$.
\item[(iii)] Any matrix in the subspace spanned by the slices of $S$ is of rank at most~$r$.
\end{itemize}
\end{theorem}
\begin{proof}
Suppose that $\sk(T) \leq r$. Properties (i) and (ii) hold for the tensor~$S$ constructed in Theorem~\ref{th:sreal}. Property (iii) follows from the corresponding property of Theorem \ref{th:sreal} and from the first part of Proposition \ref{prop:span}.

For the converse, assume that properties (i) to (iii) hold  for some tensor~$S$. We just need to show that $\sk(S) \leq r$ since $\sk(T) \leq r$ will then
follow from Theorem \ref{th:sreal}. By Theorem \ref{th:sodeco} and (i), we have a decomposition $S=\sum_{i=1}^k v_i^{\otimes 3}$ where the
$v_i$ are nonzero orthogonal vectors. By the second part of Proposition \ref{prop:span}, there is a matrix of rank $k$ in the span of the slices of~$S$.
This implies $k \leq r$ by (iii), and we have shown that $\sk(S) \leq r$ as needed.
\end{proof}

\subsection{Complex tensors} \label{sec:csymortho}

Symmetric orthogonal decompositions over~$\cc$ were first studied in \cite{koiran2019ortho} in the language of polynomials, where they are called {\em orthogonal Waring decompostions}. The corresponding set of tensors (or polynomials) was denoted $OW_n(\cc)$.
By contrast, \cite{boralevi17} studied {\em unitary} rather than orthogonal decompositions of complex tensors.
Recall from  \cite{koiran2019ortho} that a symmetric tensor $T$ of size $n$ is said to be in $OW_n(K)$
if one can write:
\begin{equation} \label{eq:symortho}
T = \sum_{i=1}^n \alpha_i (A e_i)^{\otimes 3}
\end{equation}
where $\alpha_1,\ldots,\alpha_n \in K$, $(e_1,\ldots,e_n)$ is the standard basis of $K^n$ and $A$ is an orthogonal matrix (i.e., $A^TA=I_n$).
For $K=\rr$, we recover the notion of a symetrically odeco tensor from Section \ref{sec:rortho}. In the remainder of this section we will be interested in the case $K=\cc$.
The following characterization is in the style of (\ref{eq:sodeco}) and can be found in \cite[Section 3.2]{koiran2019ortho}.
\begin{proposition} \label{prop:csodeco}
A symmetric tensor $T$ of size $n$ is in $OW_n(\cc)$ if and only if we have
$$T = \sum_{i=1}^k v_i^{\otimes 3}$$
for some integer $k \leq n$, where $v_1,\ldots,v_k$ are pairwise orthogonal non-isotropic vectors of $\cc^n$.
\end{proposition}
Here, orthogonality is defined with respect to the bilinear form $\langle u,v \rangle = u^Tv$ like in the real case. We recall that a vector $u$ is {\em isotropic} if it is self-orthogonal, i.e., $\langle u,u \rangle =0$.
In terms of slices we have the following characterization, also from \cite[Section 3.2]{koiran2019ortho}.
\begin{theorem} \label{th:csodeco}
A  symmetric tensor of size $n$ is in $OW_n(\cc)$
if and only if its slices are diagonalizable and pairwise commute.
\end{theorem}
The diagonalizability condition appears in the above theorem because, in contrast to real symmetric matrices, complex symmetric matrices are not always diagonalizable.
The following lemma is the complex analogue of Lemma~\ref{lem:extension}.
\begin{lemma} \label{lem:cextension}
Let $u_1,\ldots,u_r$ be an arbitrary family of vectors in $\cc^n$. There exists a family $v_1,\ldots,v_r$ of pairwise orthogonal non isotropic vectors of
$\cc^{r+n}$ such that $u_i$ is the orthogonal projection of $v_i$ on its first $n$ coordinates, i.e., $u_i=(v_{i1},\ldots,v_{in})$.
\end{lemma}
\begin{proof}
We are now looking for a family $w_1,\ldots,w_r$ of vectors of $\cc^{r}$ such that $\langle u_i,u_j \rangle + \langle w_i,w_j \rangle$ is equal to 0 for $i \neq j$, and is different from 0 for $i = j$.
Let $A \in M_r(\cc)$ be the symmetric matrix
with entries $A_{ij}=-\langle u_i,u_j \rangle$, and let $B=A+I_r$.
Like any complex symmetric matrix, $B$ admits a decomposition of the form  $B=LL^T$ \cite[Corollary 2.6.6]{horn13},
and we can take the rows of $L$ as our vectors $w_i$ (in particular, we obtain $\langle v_i,v_i \rangle =1$ for all $i$).
\end{proof}
With this lemma in hand, we can now give the complex analogue of Theorem~\ref{th:sreal}.
\begin{theorem} \label{th:scomplex}
Let $T$ be a complex symmetric tensor of  size $n$. For any integer $r$, $\sk(T) \leq r$ if and only if there is  a complex symmetric tensor $S$ of  size $r+n$
such that:
\begin{itemize}
\item[(i)] The slices of $S$ are diagonalizable and pairwise commute.
\item[(ii)] $T$ is a subtensor of $S$ in the sense that $T_{ijk} = S_{ijk}$ for all $1 \leq i,j,k \leq n$.
\item[(iii)] $\sk(S) \leq r$.
\end{itemize}
\end{theorem}

\begin{proof}
One shows like in the real case that  $\sk(T) \leq r$ follows from (ii) and (iii).
For the converse, assume that $\sk(T) \leq r$, and let $$T=\sum_{i=1}^r u_i^{\otimes 3}$$ be a corresponding decomposition. Let $S=\sum_{i=1}^r v_i^{\otimes 3}$ where the pairwise orthogonal non-isotropic vectors $v_i$ are given by Lemma \ref{lem:cextension}. Condition (ii) holds by construction of the $v_i$, and~(i) holds by Proposition \ref{prop:csodeco} and Theorem \ref{th:csodeco}.
Condition (iii) holds as well since $S$ is defined as a sum of $r$ tensors of rank 1.
\end{proof}
We conclude Section \ref{sec:csymortho} with an analogue of Theorem \ref{th:srealfinal}.
\begin{theorem} \label{th:scomplexfinal}
Let $T$ be a complex symmetric tensor of  size $n$. For any integer $r$, $\sk(T) \leq r$ if and only if there is  a complex symmetric tensor $S$ of  size $r+n$
such that:
\begin{itemize}
\item[(i)] The slices of $S$ are diagonalizable and pairwise commute.
\item[(ii)] $T$ is a subtensor of $S$ in the sense that $T_{ijk} = S_{ijk}$ for all $1 \leq i,j,k \leq n$.
\item[(iii)] Any matrix in the subspace spanned by the slices of $S$ is of rank at most~$r$.
\end{itemize}
\end{theorem}
\begin{proof}
Suppose that $\sk(T) \leq r$. Properties (i) and (ii) hold for the tensor~$S$ constructed in Theorem~\ref{th:scomplex}. Property (iii) follows from the corresponding property of Theorem \ref{th:scomplex} and from the first part of Proposition \ref{prop:span}.

For the converse, assume that properties (i) to (iii) hold  for some tensor~$S$. We just need to show that $\sk(S) \leq r$ since $\sk(T) \leq r$ will then
follow from Theorem \ref{th:scomplex}. By Theorem \ref{th:csodeco} and (i), we have a decomposition $S=\sum_{i=1}^k v_i^{\otimes 3}$ where the
$v_i$ are pairwise orthogonal non-isotropic vectors. In particular, the $v_i$ must be linearly independent.
By the second part of Proposition \ref{prop:span}, there is a matrix of rank $k$ in the span of the slices of~$S$.
This implies $k \leq r$ by (iii), and we have shown that $\sk(S) \leq r$ as needed.
\end{proof}

\section{Symmetric tensors: from independent decompositions
to arbitrary decompositions} \label{sec:ind}

The characterizations of symmetric rank in Section~\ref{sec:ortho} relied on earlier results about orthogonal decompositions.
In this section we give an alternative characterization which relies instead on {\em independent decompositions}.
These are symmetric decompositions involving vectors that are assumed to be linearly independent rather than
orthogonal.
The following theorem summarizes some results from~\cite{koiran19derand} regarding these decompositions.
\begin{theorem} \label{th:symequiv}
Let $K$ be the field of real or complex numbers, and let $S$ be a symmetric tensor of size $r$ over $K$ with slices $Z_1,\ldots,Z_r$. There are linearly independent vectors $v_1,\ldots,v_r \in K^r$ such that $S=\sum_{i=1}^r v_i^{\otimes 3}$ if and only if the following two conditions are satisfied:
\begin{itemize}
\item[(i)] The span of $Z_1,\ldots,Z_r$ contains an invertible matrix.
\item[(ii)]   For any invertible matrix $Z$ in this span, the $r$ matrices  ${Z}^{-1}Z_i$ commute and are diagonalizable over $K$.
\end{itemize}
\end{theorem}
\begin{proof}
This is essentially the content of \cite[Theorem 23]{koiran19derand} except that in that reference, property (ii) is replaced by:
\begin{itemize}
\item[(ii')] The slices $Z_1,\ldots,Z_r$ are simultaneously diagonalizable by congruence.
\end{itemize}
Assume first that $K=\cc$.
If (i) and (ii) hold then (ii') must hold by \cite[Theorem 7]{koiran19derand}.  Conversely, if (i) and (ii') hold then  \cite[Theorem 7]{koiran19derand} shows that:
\begin{enumerate}
\item The matrices $Z^{-1}Z_i$ commute for any invertible matrix $Z$ in the span of the $Z_i$.
\item There exists an invertible matrix $Z$ in the span such the matrices $Z^{-1}Z_i$ are diagonalizable.
\end{enumerate}
It is easily checked that  the proof of \cite[Theorem 7]{koiran19derand} implies that the above diagonalizability property holds not only for {\em some} invertible matrix $Z$ in the span, but for any invertible matrix $Z$ in the span. Hence (ii) follows from (i) and (ii'). For the field of real numbers, the arguments are very similar and can be found in \cite[Section 2.3] {koiran19derand}.
\end{proof}
As a variation on Theorem \ref{th:symequiv}, one could replace (i) and (ii) by:
\begin{itemize}
\item[(iii)]   There exists an invertible matrix $Z$ in the space of $Z_1,\ldots,Z_r$ such that that the matrices  ${Z}^{-1}Z_i$ commute and are diagonalizable over $K$.
\end{itemize}
With Theorem \ref{th:symequiv} in hand, we can now give a characterization of symmetric  tensor rank under the relatively mild assumption that the span of slices contains an invertible matrix.
\begin{theorem} \label{th:symind}
Let $K$ be the field of real or complex numbers, and let $T$ be a symmetric tensor of  size $n$ over $K$.
Assume moreover that the span of the slices of $T$ contains an invertible matrix.
For any integer $r \geq n$, $\sk(T) \leq r$ if and only if there is  a symmetric tensor $S$ of size~$r$ with slices $Z_1,\ldots,Z_r$ such that:
\begin{itemize}
\item[(i)] The span of $Z_1,\ldots,Z_r$ contains an invertible matrix.
\item[(ii)]   For any invertible matrix $Z$ in this span, the matrices  $Z^{-1}Z_i$ commute and are diagonalizable over $K$.
\item[(iii)] $T$ is a subtensor of $S$ in the sense that $T_{ijk} = S_{ijk}$ for all $1 \leq i,j,k \leq n$.
\end{itemize}
\end{theorem}
\begin{proof}
Suppose that $T=\sum_{i=1}^r u_i^{\otimes 3}$ where $u_1,\ldots,u_r \in K^n$. Since the span of the slices of $T$ contains an invertible matrix, the family $u_1,\ldots,u_r$
must be of rank $n$ by Proposition~\ref{prop:span}. Consider the $r \times n$ matrix having the $u_i$ as row vectors. We can attach to this matrix
$r-n$ column vectors in order to obtain a matrix $V$ of rank $r$. Let $v_1,\ldots,v_r \in K^r$ be the row vectors of $V$
and let $S=\sum_{i=1}^r v_i^{\otimes 3}$. Property (iii) holds for $S$ by construction. Properties~(i) and (ii) follow from Theorem \ref{th:symequiv} since the family $v_1,\ldots,v_r$ is of rank $r$. Note that  (i)  also follows from Proposition \ref{prop:span}.

For the converse, assume that properties (i) to (iii) hold for $S$. By Theorem~\ref{th:symequiv} there are vectors $v_1,\ldots,v_r$ such that
 $S=\sum_{i=1}^r v_i^{\otimes 3}$. By (iii) we have $T=\sum_{i=1}^r u_i^{\otimes 3}$
 where $u_1,\ldots,u_r$ are obtained from the first $n$ coordinates of $v_1,\ldots,v_r$.
\end{proof}

\section{Ordinary tensors: from orthogonal decompositions to arbitrary decompositions}
\label{sec:oortho}

The characterizations of tensor rank given in this section rely on appropriate generalizations of the orthogonal decompositions
of Section~\ref{sec:ortho} to the setting of ordinary tensors.

\subsection{Real tensors} \label{sec:roortho}

Following~\cite{boralevi17}, a real ordinary tensor of size $n$ is said to be {\em odeco}
if one can write
\begin{equation} \label{eq:odeco}
T = \sum_{i=1}^ k u_i \otimes v_i \otimes w_i
\end{equation}
where each of the 3 lists $(u_1,\ldots,u_k)$, $(v_1,\ldots,v_k)$, $(w_1,\ldots,w_k)$ is made of~$k$ nonzero, pairwise orthogonal vectors of $\rr^n$.
A characterization of odeco tensors by degree 2 equations was obtained in ~\cite{boralevi17}.
Like in Section \ref{sec:rortho} we will work instead with a characterization in terms of slices:

\begin{theorem} \label{th:odeco}
For a real tensor $T$ of size $n$, the two following properties are equivalent:
\begin{itemize}
\item[(i)] If $(T_1,\ldots,T_n)$ denotes the tuple of $x$-slices of $T$, or its tuple of $y$-slices, or its tuple of $z$-slices then the matrices $T_k T_l^T$ and $T_k^T T_l$ are symmetric for all $k, l \in \{1,\ldots,n\}$.
\item[(ii)] $T$ is odeco.
\end{itemize}
\end{theorem}
This result from \cite[Section 4]{koiran2019ortho} is the ordinary analogue of Theorem \ref{th:sodeco}.
As pointed out in that paper, property (i) implies in  particular that the matrices $T_k T_l^T$ pairwise commute, and
that the matrices $T_k^T T_l$ pairwise commute.
The following characterization of tensor rank is the ordinary analogue of Theorem \ref{th:sreal}.
\begin{theorem} \label{th:real}
Let $T$ be a real tensor of size $n$. For any integer~$r$, $\rk(T) \leq r$ if and only if there is  a real tensor $S$ of size $r+n$
such that:
\begin{itemize}
\item[(i)] The $x$, $y$ and $z$-slices of $S$ satisfy property (i) from Theorem \ref{th:odeco}.
\item[(ii)] $T$ is a subtensor of $S$ in the sense that $T_{ijk} = S_{ijk}$ for all $1 \leq i,j,k \leq n$.
\item[(iii)] $\rk(S) \leq r$.
\end{itemize}
\end{theorem}
The proof is omitted since it is a straightforward adaptation of the proof of Theorem \ref{th:sreal} (instead of Theorem \ref{th:sodeco}, we just need to evoke Theorem \ref{th:odeco}).
The final result of Section \ref{sec:roortho} is the ordinary counterpart of Theorem \ref{th:srealfinal}.
Its proof is omitted for the same reason.
\begin{theorem} \label{th:realfinal}
Let $T$ be a real tensor of  size $n$. For any integer~$r$, $\rk(T) \leq r$ if and only if there is  a real tensor $S$ of size $r+n$
such that:
\begin{itemize}
\item[(i)] The $x$, $y$ and $z$-slices of $S$ satisfy property (i) from Theorem \ref{th:odeco}.
\item[(ii)] $T$ is a subtensor of $S$ in the sense that $T_{ijk} = S_{ijk}$ for all $1 \leq i,j,k \leq n$.
\item[(iii)] Any matrix in the subspace spanned by the $z$-slices of $S$ is of rank at most~$r$.
\end{itemize}
\end{theorem}

\begin{remark}
Let $T$ be a real tensor of  size $n$, and let $S$ be the tensor constructed from $T$ in the above theorem. Property (iii) is about
the $z$-slices of $S$, but the $x$ and $y$ slices of $S$ also satisfy the same property.
A similar remark will apply to Theorem \ref{th:complexfinal} in Section \ref{sec:coortho}.
\end{remark}

\subsection{Complex tensors} \label{sec:coortho}

Like in the symmetric case, orthogonal decompositions of complex ordinary tensors were first studied in \cite{koiran2019ortho}.
The corresponding set of tensors (or polynomials) was denoted $OT_n(\cc)$.
Let $K$ be the field of real or complex numbers.
Recall from  \cite{koiran2019ortho} that a  tensor $T$ of  size $n$ is said to be in $OT_n(K)$
if one can write:
\begin{equation} \label{eq:symortho}
T = \sum_{i=1}^n \alpha_i (A e_i) \otimes (Be_i) \otimes (Ce_i)
\end{equation}
where $\alpha_1,\ldots,\alpha_n \in K$, $(e_1,\ldots,e_n)$ is the standard basis of $K^n$ and $A,B,C$ are three orthogonal matrices.
For $K=\rr$, we recover the notion of an odeco tensor from Section \ref{sec:roortho}. In the remainder of this section we will be interested in the case $K=\cc$.
The following characterization is the ordinary analogue of Proposition \ref{prop:csodeco}.
\begin{proposition} \label{prop:codeco}
A tensor $T$ of size $n$
is in $OT_n(\cc)$ if and only if we have
$$T = \sum_{i=1}^k u_i \otimes v_i \otimes w_i$$
for some integer $k \leq n$, where each of the 3 lists $(u_1,\ldots,u_k)$, $(v_1,\ldots,v_k)$, $(w_1,\ldots,w_k)$ is made of $k$  pairwise orthogonal non-isotropic vectors of $\cc^n$.
\end{proposition}
In terms of slices we have the following characterization~\cite[Section 4.2]{koiran2019ortho}.
\begin{theorem} \label{th:ot}
  A complex tensor $T$ of  size $n$ admits an orthogonal decomposition iff the $x$-slices of $T$ satisfy the following conditions:
  \begin{itemize}
  \item[(i)] for each $k$, $X_k^T X_k$ is diagonalizable and
    $\rk X_k = \rk X_k^T X_k$,
  \item[(ii)] the matrices $X_k X_l^T$ and $X_k^T X_l$
  are symmetric for all $k,l \in \{1,\ldots,n\}$,
  \end{itemize}
  and the $y$ and $z$-slices satisfy the same conditions.
  \end{theorem}
  The next result is the ordinary analogue of Theorem~\ref{th:scomplex}, and the complex analogue of Theorem~\ref{th:real}.
  \begin{theorem} \label{th:complex}
Let $T$ be a complex tensor of  size $n$. For any integer $r$, $\rk(T) \leq r$ if and only if there is  a complex  tensor $S$ of size $r+n$
such that:
\begin{itemize}
\item[(i)] The $x$, $y$ and $z$-slices of $S$ satisfy the conditions of Theorem \ref{th:ot}.
\item[(ii)] $T$ is a subtensor of $S$ in the sense that $T_{ijk} = S_{ijk}$ for all $1 \leq i,j,k \leq n$.
\item[(iii)] $\rk(S) \leq r$.
\end{itemize}
\end{theorem}
The proof is omitted since it is a straightforward adaptation of the proof of Theorem \ref{th:scomplex} (instead of Proposition \ref{prop:csodeco} and Theorem \ref{th:csodeco}, we just need to apply Proposition \ref{prop:codeco} and Theorem \ref{th:ot}).
The final result of Section \ref{sec:coortho} is the ordinary counterpart of Theorem \ref{th:scomplexfinal}, and the complex counterpart of
Theorem \ref{th:realfinal}. Its proof is omitted for the same reason.
 \begin{theorem} \label{th:complexfinal}
Let $T$ be a complex tensor of  size $n$. For any integer $r$, $\rk(T) \leq r$ if and only if there is  a complex  tensor $S$ of  size $r+n$
such that:
\begin{itemize}
\item[(i)] The $x$, $y$ and $z$-slices of $S$ satisfy the conditions of Theorem \ref{th:ot}.
\item[(ii)] $T$ is a subtensor of $S$ in the sense that $T_{ijk} = S_{ijk}$ for all $1 \leq i,j,k \leq n$.
\item[(iii)] Any matrix in the subspace spanned by the $z$-slices of $S$ is of rank at most~$r$.
\end{itemize}
\end{theorem}

\section{Ordinary tensors: from independent decompositions to arbitrary decompositions}
\label{sec:oind}

In this section
we generalize the notion of {\em independent decomposition} from Section~\ref{sec:ind} to the setting of ordinary tensors.
As it turns out, we only need to assume that each of the two families $(u_1,\ldots,u_r)$,
$(v_1,\ldots,v_r)$ in~(\ref{eq:decomp})  is made of linearly independent vectors; no assumption is made about the
family $(w_1,\ldots,w_r)$.
 Then we give a characterization of the set of decomposable tensors, and we use it to prove Theorems \ref{th:embedding} and \ref{th:indintro}.

\subsection{Independent decompositions of ordinary tensors}

\begin{theorem}[simultaneous diagonalization by equivalence] \label{th:simdiag}
  Let $A_1,\ldots,A_k$ be
  matrices of size $n$
  and assume that their span contains an invertible matrix~$A$.
  There are   diagonal matrices $D_i$ and two nonsingular matrices
  $P,Q \in M_n(K)$ such that
$A_i = P D_i Q$ for all $i=1,\ldots,k$ if and only if the $k$ matrices $A^{-1}A_i$ ($i=1,\ldots,k$) form a commuting family of diagonalizable matrices.
\end{theorem}
\begin{proof}
We will show this for the special case $A=A_1$. The general case follows easily since the tuple $(A_1,\ldots,A_k)$ is simultaneously diagonalizable by equivalence if and only if the same is true of the tuple $(A,A_1,\ldots,A_k)$.

  Suppose first that $A_i = P D_i Q$ where $P,Q$ are nonsingular and the $D_i$ diagonal. Since $A_1$ is invertible, the same is true of
  $D_1$ and we have $A_1^{-1}A_i = Q^{-1}D_1^{-1}D_iQ$.
  These matrices are therefore diagonalizable, and they pairwise commute.

  Assume conversely that the $A_1^{-1}A_i$ form a commuting family of diagonalizable matrices. This is well known to be a necessary and sufficient condition
  for simultaneous diagonalization by similarity~\cite[Theorem~1.3.21]{horn13}: there must exist a nonsingular
  matrix $Q$ and diagonal matrices $D_2,\ldots,D_k$ such that
  $A_1^{-1}A_i = Q^{-1}D_iQ$ for $i=2,\ldots,k$. Let $P=A_1Q^{-1}$.
  We have $A_1=PD_1Q$ where $D_1$ is the identity matrix, and for $i \geq 2$
  we have $PD_iQ = A_1Q^{-1}D_iQ = A_1(A_1^{-1}A_i)= A_i.$
\end{proof}

\begin{theorem} \label{th:indordi}
Let $S$ be a tensor
of format $r \times r \times p$ over $K$, with an invertible matrix~$Z$ in the span of its $z$-slices.
The following properties are equivalent:
\begin{itemize}
\item[(i)] There is a family  $(w_1,\ldots,w_r)$ of vectors of $K^p$ and  two linearly independent families $(u_1,\ldots,u_r)$,
$(v_1,\ldots,v_r)$   of vectors of $K^r$ such that
$$S=\sum_{i=1}^r u_i \otimes v_i  \otimes w_i.$$
\item[(ii)]  The $p$ matrices  ${Z}^{-1}Z_i$ commute and are diagonalizable over $K$.
\end{itemize}
\end{theorem}
\begin{proof}
By Proposition~\ref{prop:slices}, (i) is equivalent to the existence of two invertible matrices $U$ and $V$ and of diagonal matrices $D_1,\ldots,D_p$ of size $r$
such that the $z$-zlices of $S$ satisfy $Z_i=U^TD_iV$ for $i=1,\ldots,p$. This is in turn equivalent to (ii) by Theorem~\ref{th:simdiag}.
\end{proof}

\subsection{A characterization of tensor rank} \label{subsec:oind}

We can derive from Theorem \ref{th:indordi} a characterization of tensor rank under the relatively mild assumption that the spans of
$z$-slices
contains an invertible matrix. This is the ordinary analogue of Theorem \ref{th:symind}. This result already appears as Theorem~\ref{th:indintro} in Section~1. We reproduce its statement below for the reader's convenience.
\begin{theorem} \label{th:ind}
Let $T$ be a tensor
of format $n \times n \times p$ over $K$.
Assume moreover that the span of the
 $z$-slices of $T$
 contains an invertible matrix.
For any integer $r \geq n$, $\rk(T) \leq r$ if and only if there is  a  tensor $S \in K^{r \times r \times p}$ with  $z$-slices $Z_1,\ldots,Z_p$
such that:
\begin{itemize}
\item[(i)] The span of $Z_1,\ldots,Z_p$
contains an invertible matrix.
\item[(ii)]   For any invertible matrix $Z$ in the span of $Z_1,\ldots,Z_p$, the matrices  $Z^{-1}Z_i$ commute and are diagonalizable over $K$.
\item[(iii)] $T$ is a subtensor of $S$ in the sense that $T_{ijk} = S_{ijk}$ for  $1 \leq i,j \leq n$ and $1 \leq k \leq p$.
\end{itemize}
\end{theorem}

\begin{proof}
Suppose that $T=\sum_{i=1}^r u_i \otimes v_i \otimes w_i$ with  $u_i, v_i \in K^n$ and $w_i \in K^p$. Since the span of the
$z$-slices of $T$
contains an invertible matrix, it follows from Proposition~\ref{prop:span} that each of the 2 families $(u_1,\ldots,u_r)$ and $(v_1,\ldots,v_r)$
must be of rank $n$. Consider the $r \times n$ matrix having the $u_i$ as row vectors. We can attach to this matrix
$r-n$ column vectors in order to obtain a matrix~$U'$ of rank $r$. We can likewise obtain a matrix $V' \in GL_r(K)$
from the~$v_i$.
Let $(u'_1,\ldots,u'_r)$ and $(v'_1,\ldots,v'_r)$
be the 2 families of vectors of $K^r$ obtained respectively from the rows of $U'$ and $V'$.
Finally, let  $S=\sum_{i=1}^r u'_i \otimes v'_i \otimes w_i$. Property~(iii) holds for~$S$ by construction. Properties~(i) and (ii) follow from Theorem~\ref{th:indordi} since the 2 families $(u_1,\ldots,u_r)$ and $(v_1,\ldots,v_r)$
are made of linearly independent vectors.

For the converse, assume that properties (i) to (iii) hold for $S$. By Theorem~\ref{th:indordi} there are vectors $u'_i,v'_i,w_i$ such that
 $S=\sum_{i=1}^r u'_i \otimes v'_i \otimes w_i$. By (iii) we have $T=\sum_{i=1}^r u_i \otimes v_i \otimes w_i$
 where $u_i$ and $v_i$ are obtained respectively from the first $n$ coordinates of $u'_i$ and $v'_i$.
\end{proof}

\subsection{Making slices commute again} \label{sec:commuteagain}

Compared to e.g. Theorem~\ref{th:scomplexfinal}, there is an unpleasant complication in Theorem \ref{th:ind}:
the commutation property that we have obtained is not directly for the slices $Z_i$ of $S$, but for matrices of the form $Z^{-1}Z_i$.
In Theorem \ref{th:commuteagain} we will obtain a simpler commutation property, directly for the slices of $S$.
The price to pay is that we do not obtain an exact characterization of tensor rank like in Theorems \ref{th:scomplexfinal} or
 \ref{th:ind}.
 Toward the proof of Theorem \ref{th:commuteagain} we need the following simple fact, already used in \cite{strassen83}.
\begin{lemma} \label{lem:identity}
Let $U$ and $V$ be two $r \times n$ matrices
such that $U^TV=I_n$. Then $r \geq n$, and one can add  $r-n$ columns to $U$ and $V$ in order to obtain
two $r \times r$ matrices which satisfy $U'^TV'=I_r$.
\end{lemma}
\begin{proof}
We have $r \geq n$ since $\rk(U^TV) \leq \max(\rk(U),\rk(V))$.
{ Let us add to $V$ the columns of a $r \times (r-n)$ matrix $B$ such that $\Ima(B) = \ker (U^T)$.
The resulting matrix $V'$ is invertible since $\Ima(V) \cap \ker (U^T) = \{0\}$.
Its inverse is obtained by adding to $U^T$ the rows of a matrix $A^T$ such that $\ker(A^T) = \Ima(V)$.
}
\end{proof}

\begin{theorem} \label{th:commuteagain}
Let $T$ be a tensor of
format  $n \times n \times p$ over $K$
and let $r=\rk(T)$.
There exists  a  tensor $S$
of format~$(r+n) \times (r+n) \times p$ with  $z$-slices $Z_1,\ldots,Z_{p}$ such that:
\begin{itemize}
\item[(i)]   The  $Z_i$ commute and are diagonalizable over $K$.
\item[(ii)] $T$ is a subtensor of $S$ in the sense that $T_{ijk} = S_{ijk}$ for all $1 \leq i,j \leq n$ and $1 \leq k \leq p$.
\end{itemize}
\end{theorem}
Note that this is just a restatement of Theorem~\ref{th:embedding} since we can form a tensor $T$ from any tuple of matrices.
\begin{proof}
This is a variation on the proof of Theorem \ref{th:ind}, with some additional elements coming from the proof of Strassen's theorem~\cite{strassen83}. Very roughly, the two main steps are: to construct a tensor $T'$  of rank at most $r+n$
obtained from $T$
by addition of a  $(1+p)$-th slice equal to the identity matrix; and then to apply the construction of Theorem \ref{th:ind} to $T'$ in order to obtain
a tensor $S'$ with $p+1$ slices and a last slice $Z_{p+1}$ equal to the identity matrix. Theorem~\ref{th:ind} applied with $Z=Z_{p+1}$ then shows that the slices of $S'$ must commute. We can therefore take for $S$ the tensor made of the first $p$ slices of $S'$.

Let us now describe the construction of $T'$.
Consider a decomposition $T=\sum_{i=1}^r u_i \otimes v_i  \otimes w_i$.  We will take
$T'=\sum_{i=1}^{r+n} u'_i \otimes v'_i  \otimes w'_i$ where:
\begin{enumerate}
\item For $i \leq r$, $u'_i=u_i$, $v'_i=v_i$ and $w'_i \in K^{p+1}$ is obtained from $w_i$ by addition of a last coordinate
$w'_{i,p+1}=1$.
\item For $i>r$, $w'_i$ is equal to  $e_{p+1}$, the $(1+p)$-th vector of the standard basis of $K^{p+1}$. It will be important at the end of the proof that we chose $w'_{i,p+1}=1$ for all $i$.
\end{enumerate}
These two conditions ensure that the first $p$ slices of $T'$ are those of $T$. Moreover, in the last $n$ terms
$\sum_{i>r} u'_i \otimes v'_i \otimes e_{p+1}$ of the decomposition of~$T'$,
 the factor $\sum_{i>r} u'_i \otimes v'_i$ can be made equal to any matrix of size $n$ by an appropriate choice of the $u'_i$ and $v'_i$. In particular, we can choose these vectors so that $T'$ has the identity matrix as its last slice.

Next we describe the construction of $S'$ from $T'$.
Since $T'$ has a slice of rank $n$ (the last one),  by Proposition~\ref{prop:span} the two families $(u'_1,\ldots,u'_{r+n})$
and $(v'_1,\ldots,v'_{r+n})$ must be of rank $n$.
We can now proceed as in the proof of  Theorem \ref{th:ind}. Namely, let $U'$ be the $(r+n) \times n$ matrix having the $u'_i$ as row vectors.
We can attach to this matrix
$r$ column vectors in order to obtain a matrix $U''$ of rank $r+n$. We can likewise obtain a matrix $V'' \in GL_{r+n}(K)$
from the $v'_i$.
 By construction, $T'$ is a subtensor of
 \begin{equation} \label{eq:stensor}
 S'=\sum_{i=1}^{r+n} u''_i \otimes v''_i \otimes w'_i
 \end{equation}
 where the $u''_i$ and $v''_i$ are respectively the rows vectors of $U''$ and $V''$.
 Moreover, property (ii) in Theorem \ref{th:ind} shows that we have the following property for the slices $Z_i$ of $S'$:
 \begin{itemize}
 \item[(ii')]  For any invertible matrix $Z$ in the span of $Z_1,\ldots,Z_{p+1}$, the matrices  $Z^{-1}Z_i$ commute and are diagonalizable over $K$.
 \end{itemize}
 Therefore, if we can take $Z=I_{r+n}$ in (ii') we have obtained Theorem~\ref{th:commuteagain}.(i). As a result, all that remains to be done is to show that we can obtain $Z_{p+1}=I_{r+n}$. We will obtain this property by a careful choice of the matrices $U''$ and~$V''$.
 First, note that since $I_n$ is the last slice of $T'$ we have $$U'^TD_{p+1}V'=I_n$$ by~(\ref{eq:slices}), where
 $D_{p+1} = \diag(w_{1,p+1},\ldots,w_{r+n,p+1})$. Remembering that we chose $w_{i,p+1}=1$ for all $i$, this yields $U'^TV'=I_n$.
 By Lemma~\ref{lem:identity}  we can add $r$ columns to $U'$ and $V'$ in order to obtain $(r+n)\times (r+n)$ matrices $U''$ and $V''$ which satisfy
 $U''^T V'' = I_{r+n}$. We conclude that the last slice of the tensor~$S$ in~(\ref{eq:stensor}) is equal to
 $U''^TD_{p+1}V''=U''^TV''=I_{r+n}$, as needed. Finally, as announced at the beginning of the proof we take  for $S$ the tensor made of the first $p$ slices of $S'$.
 \end{proof}

As our final result we observe that Theorem~\ref{th:commuteagain} (i.e., Theorem~\ref{th:embedding})  is tight up to the additive term $n$.
\begin{theorem} \label{th:tight}
Let $(A_1,\ldots,A_p)$ be a tuple of $p$ matrices of $M_n(K)$.
If these matrices can be embedded as submatrices in a commuting tuple of
$p$ diagonalizable matrices of size $N$, we must have $N \geq \rk(T)$ where $T$ denotes the tensor with slices
$(A_1,\ldots,A_p)$.
\end{theorem}
\begin{proof}
Let $(Z_1,\ldots,Z_p)$ be the commuting tuple and let $S$ be the tensor with slices $Z_1,\ldots,Z_p$. Since the $Z_k$ commute and are diagonalizable, they are simultaneously diagonalizable: there are diagonal matrices $D_1,\ldots,D_p$ and  an invertible matrix $P$ such that $Z_k =  P^{-1} D_k P$
for $1 \leq k \leq p$.
By Proposition \ref{prop:slices} we have $\rk(S) \leq N$, and $\rk(T) \leq N$ follows since $T$ is a subtensor of $S$.
\end{proof}

{\small

\section*{Acknowledgments}

Discussions with Joseph Landsberg led to a more extensive presentation of prior work, and in particular of rank methods
and barrier results. The embedding in~(\ref{eq:2n}) was communicated by Jeroen Zuiddam.


TITLE: Delta Dirac and duality property
QUESTION [3 upvotes]: I know that the property of duality says:
$$x(t) \iff X(f)$$
$$X(t) \iff x(-f) "="x(t=-f)$$
and I know that:
$$\delta(t-t_0) \iff exp(-j2\pi ft_0)$$
If I apply the duality property, I get:
$$exp(-j2\pi f_0t) \iff \delta(-f-f_0)$$
$$exp(j2\pi f_0t) \iff \delta(f-f_0)$$
instead the correct result is:
$$exp(j2\pi f_0t) \iff \delta(f+f_0)$$
Why?
Thank you for your help.

REPLY [6 votes]: I think you're getting confused between $t$ and $f$ , Duality says

$$x(t) \Leftrightarrow X(\omega) \implies X(t)\Leftrightarrow2\pi x(-\omega) $$
  Or in terms of $f$
  $$x(t) \Leftrightarrow X(f) \implies X(t)\Leftrightarrow x(-f) $$

So for $\delta(t-t_0)$
$$\delta(t-t_0)  \Leftrightarrow \mathrm{exp}(-jt_0 2\pi f) \implies \mathrm{exp}(-jt_02\pi t) \Leftrightarrow \delta(-f-t_{0})=\delta(f+t_0)$$
And for $\delta(t+t_0)$
$$\delta(t+t_0)  \Leftrightarrow \mathrm{exp}(jt_0 2\pi f) \implies \mathrm{exp}(jt_02\pi t) \Leftrightarrow \delta(-f+t_{0})=\delta(f-t_0)$$
Note that $\delta(t)$ is even function
Please let me know if i can improve my answer somehow , thanks !


TITLE: Grip of the train wheels
QUESTION [10 upvotes]: How do the wheels of a train have sufficient grip on a metal track? I mean both of the surfaces are smooth (and not flexible) and it is okay if there is no inclination, but how about on an inclined track?

REPLY [6 votes]: Sliding is prevented by friction and the friction force is equal to the product of the weight - the perpendicular force - and the dimensionless coefficient of static friction.
The coefficient of static friction between steel and steel can be as high as 0.78 so the angle would have to be hugely non-horizontal for the train to slide. And a lot of acceleration may be added, too.
The lowest coefficient of static friction in wet and greasy conditions may be 0.05 which is approximately the angle in radians where one could start to get worried. It is just 3 degrees and if there's lot of oil everywhere on the tracks, the train may get unsafe already for these small angles. However, in reality, the coefficient never drops this low and 15 degrees is usually a safe angle.
See also:

http://en.wikipedia.org/wiki/Rail_adhesion

Note that the coefficient of static friction is higher than the coefficient of kinetic friction so the hardest thing is to start the sliding. Once the train starts to slide, it is more likely that it will continue to do so.
All the text above was about the sliding - the stability in the front-rear direction. The stability in the left-right direction is guaranteed by the shape of the wheels:


TITLE: Wave equation with variable speed coefficient
QUESTION [9 upvotes]: Consider the wave equation initial value problem in $\mathbb R^3$ with spatially variable wave speed, denoted by
\begin{align*}
\frac{\partial^2}{\partial t^2}u(x,t)-c^2(x)\Delta u(x,t)&=0\hspace{.2in}\text{in }\mathbb R^3\times(0,\infty),\\
u(x,0)&=f(x),\\\frac{\partial}{\partial t}u(x,0)&=g(x).
\end{align*}
My question: Is there a way to explicitly write down a solution similar to Kirchhoff's formula for the case of constant speed $c(x)=c_0$?
Intuitivly, i would expect the solution $u(x_0,t_0)$ for fixed space and time to be dependent on values of spherical integrals of $f$ and $g$ as in the constant speed case, but in a sound-speed dependent metric.
This is related to a similar question concerning a wave equation in 1 dimension: Wave propagation with variable wave speed

REPLY [10 votes]: There is an extensive literature on wave equations with variable coefficients, which are equivalent to wave equations on curved spacetime - as in the monograph by Friendlander. Depending on what you are willing to accept as 'explicit', the answer is that yes, there is an explicit generalisation of the Kirchhoff integral. However, it is very difficult to calculate the coefficients of the data $f,g$ in this integral, which are determined by the retarded Green function $G_R$ of the wave operator: $$\square = \partial_t^2 - c(x)\Delta.$$ This Green function is intimately related to the geometry of the spacetime with line element $ds^2=dt^2-c(x)d\vec{x}\cdot d\vec{x}$. In order to calculate $G_R$, you essentially need to fully solve the geodesic equations obtained by extremising the action $\int ds$.
The retarded Green's function satisfies
$$ \square G_R(t,x;t',x')=-4\pi\delta_4(t,x;t',x'),$$ where $\delta_4$ is the 4-dimensional Dirac distribution. Then the generalized Kirchhoff formula allows us to explicitly write down the value of a solution $\Psi$ of the wave equation at a point $(t,x)$ to the future of an initial data hypersurface $\Sigma^\prime=\{(t',x'):x'\in\mathbb{R}^3\}$:
$$ \Psi(t,x)=-\frac{1}{4\pi}\int_{\Sigma^\prime}(G_R(t,x;t',x')g(x')-f(x')\partial_{t'}G_R(t,x;t',x'))d\Sigma^\prime,$$
where $d\Sigma^\prime=c^{3/2}(x')d_3x'$ is the volume element on $\Sigma^\prime$.
These things (Green's function, waves in curved spacetime) are of great interest in General Relativity, and the GR literature is a good place to look for more details. In particular, I recommend starting with Poisson's Living Review article which covers the geometrical background in a very readable way. You'll find details here (and in the citations) on how to calculate $G_R$, which is required for practical applications of the Kirchhoff formula.


TITLE: MLE coin toss problem
QUESTION [0 upvotes]: Given a coin with an unknown bias and the observation of $N$ heads and $0$
tails, what is expected probability that the next flip is a head?
i want to solve with MLE, not Bayesian analysis.
My attempt:
For any value of p , the probability of k Heads in n tosses is given by
$\binom{n}{k} p^k \left ( 1-p \right )^{n-k}$
Consider the maximization problem:
$\frac{\partial p^k \binom{n}{k} (1-p)^{n-k}}{\partial p}=0$
$\hat{p}=\frac{k}{n}$
and I'm stuck here. Thank you.
Answer: $\frac{n+1}{n+2}$

REPLY [0 votes]: we observe $k=N$ heads in $N$ trials and want to determine the unknown probability $p$ and the accuracy of the estimate. The maximum likelihood estimate is the value of $p$ giving the largest probability for the observed data.
$0\leq p\leq 1$
$Unif(0, 1)$ and the beta distribution where $α = 1$, $β = 1$ in our case.
Lets find the posterior distribution of p for a prior, π(p) ∼ Beta(α, β)
$\pi (p)=\frac{1}{B(\alpha ,\beta )}p^{\alpha -1}\left ( 1-p \right )^{\beta -1}$
$f(k|p)=\binom{n}{k}p^{k}(1-p)^{n-k}$
$f(p|k)=\frac{f(k|p)}{f_{K}k}\pi(p)$
$\propto p^{k+\alpha -1}(1-p)^{n-k+\beta -1}$
Based on this we can see that $f(p|k)$ has a Beta(k+α, n−k+β) distribution.
so $\beta=1$ and $\alpha=1$
the likelihood is proportional to the beta distribution, with parameters $k+1$ and $n-k+1$.
In our problem $N$ Heads in $N$ tosses.
N=k
This partial derivative is $0$ at the maximum likelihood estimates;
$\frac{\partial p^{k+1} (1-p)^{n-k+1}}{\partial p}=0$
$p=\frac{k+1}{n+2}$
$n=k$ $\Rightarrow$ $p=\frac{n+1}{n+2}$
(Note that it isn’t necessary to find $f_K(k)$ explicitly and we can ignore the normalizing constants of both the Likelihood and Prior.)


TITLE: Could quantum randomness be transformed into classical, macroscale randomness?
QUESTION [0 upvotes]: If measurements of quantum phenomena can show results that are truly random wouldn't it be possible to establish a macroscale-dependence on such a non-statistical result and thereby introduce randomness and an interruption of determinism - if it exists - into the classical realm?
This is similar to the Schrödinger's Cat thought experiment, about which Schrödinger wrote:

It is typical of these cases that an indeterminacy originally restricted to the atomic domain becomes transformed into macroscopic indeterminacy, which can then be resolved by direct observation.

Some speculate that "determinism can emerge from underlying indeterminism (via the law of large numbers)" and that "the universe could be conceived of as having alternating layers of causality and chaos".
Here it says:

According to several standard interpretations of quantum mechanics, microscopic phenomena are objectively random. That is, in an experiment that controls all causally relevant parameters, some aspects of the outcome still vary randomly. For example, if a single unstable atom is placed in a controlled environment, it cannot be predicted how long it will take for the atom to decay—only the probability of decay in a given time. Thus, quantum mechanics does not specify the outcome of individual experiments but only the probabilities. Hidden variable theories reject the view that nature contains irreducible randomness: such theories posit that in the processes that appear random, properties with a certain statistical distribution are at work behind the scenes, determining the outcome in each case.

And here:

This debate is relevant because it is easy to imagine specific situations in which the arrival of an electron at a screen at a certain point and time would trigger one event, whereas its arrival at another point would trigger an entirely different event (e.g. see Schrödinger's cat - a thought experiment used as part of a deeper debate).

REPLY [1 votes]: I guess that you could, in principle, make a stochastic classical theory that is able to reproduce QM, but, as proven by EPR, such a theory needs to be non-local. In an EPR-Bohm test, for example, if you want the result of the first measurement to be "truly" random you need to accept that this measurement instantly "forces" the distant particle to get the oposite spin.


TITLE: Complex structures on $R^{2N}$ with complex annulus
QUESTION [4 upvotes]: Let $M$ be a complex manifold of dimension $N\ge2$ such that
$\qquad$(1) $M$ is diffeomorphic to $R^{2N}$,
$\qquad$(2) There is a compact set $K\subseteq M$ such that $M\setminus K$ is biholomorphic to $C^N\setminus \bar B_1$.
Must $M$ be biholomorphic to $C^N$?
I don't know if the problem is open, or easy. I'm interested in related problems and references.

REPLY [5 votes]: Consider, for $N=1$, the case where  $M$ is the open unit disk $B_1$: diffeomeorphic to $\mathbb{R}^2$,  not biholomorphic to $\mathbb{C}$. The compact $K:=\{0\}$ is actually such that $M\setminus K$ is biholomorphic to $\mathbb{C}\setminus \bar{B_1}$ via $z\mapsto 1/z$, disproving the conjecture.


TITLE: Finding length of hypotenuse T
QUESTION [0 upvotes]: I have the question:

And I am asked to find the tension, T, in the rope.
I have drawn a triangle:

And have tried to use trigonometry to find T. However, the solutions say that T should be 17.8N and I am not sure how this is achieved.

REPLY [0 votes]: The key is that the bar is attached to the wall at $A$, so it will not slide up or down.  So the only thing needed for equilibrium is that the net torque about point $A$ balance to zero.
The torque due to the bar weight is
$$
\tau_b = 20 \mbox{ N} \cdot 0.4 \mbox{ m} = 8 \mbox{ N-m}
$$
The torque due to the tension of the rope is
$$
\tau_r = T_y \cdot 0.7 \mbox{ m}
$$
where $T_y$ is the upward component of the force exerted by the rope
$$
T_y = T\sin(40^\circ)
$$
Solving
$$
T\sin(40^\circ) \cdot  0.7 \mbox{ m}= 8 \mbox{ N-m}\\
T = \frac{8}{0.7 \sin(40^\circ)} \frac{\mbox{ N-m}}{\mbox{ m}}\approx 17.78 \mbox{ N}
$$


TITLE: Arc length differential same as function differential for vector valued function?
QUESTION [0 upvotes]: I'm learning how to calculate curvature and one of the steps is to calculate $$\frac{dT}{ds}$$
$T$ is the tangent vector to the curve and $ds$ is arc length. But here in this video, he uses says we can calculate this by finding:
$$\frac{||\frac{dT}{dt}||}{||\frac{d\vec{s}}{dt}||}$$
So why can we use $ds$ and $d\vec{s}$ both the same in this context? One is describing arc length, and one is describing the differential vector. I'm thinking they're supposed to be the same but I'd like geometric intuition, because different speeds at which this function is parameterized changes the derivative of the vector valued function. For example, if the function was modified to trace the curve twice as fast, $\frac{d\vec{s}}{dt}$ would be larger, so I don't quite see how it could trace out arc length.

REPLY [0 votes]: In this context $ds=\sqrt{(dx)^2+(dy)^2}=\sqrt{x'^2+y'^2}dt=\Vert s'(t)\Vert dt$. He talks in the video about "tiny changes", he is using the idea of differential ($ds$, $dt$) to make calculations.


TITLE: bare Phonon and Symmetry Breaking
QUESTION [7 upvotes]: In condensed matter physics, the phonon is considered as a quasiparticle which is a result of the quantization of lattice vibrations. In many textbooks on solid state physics, it can be done if we consider a harmonic approximation, which means that if we consider the ions form a periodic lattice, and are moving around this position, the restoring force is proportional to the square of the displacement, we can get acoustic phonon, whose frequency $\omega_q$ goes to 0 as $q\rightarrow0$, and this can be understand as an example of Goldstone mode;
However, as mentioned in the book by Mahan, this acoustic phonon is a result of electron screening of the bare phonon, where the bare phonon is just a plasma mode of ions, whose frequency is finite as $q\rightarrow0$. Seems plasma is related to a continuum model of ions.
So I wonder how to connect these two ideas together and give a unified description of phonon. PS: can the ions form a periodic lattice without electrons?

REPLY [5 votes]: @GerryHarp's answer contains the gist of the main idea, but there is a point that doesn't quite make sense: There is no such thing as bare ions crystal in solid state physics.
To answer your last question: The "bare phonon frequencies" definitely do not refer to phonon frequencies in the absence of electrons. In fact, an ion crystal without electrons is utterly unstable except in the 1-d case depicted in the previous answer. In 2 or more dimensions and in the absence of the electron background, ion-ion repulsion instantly flings the ions to whatever the boundary of the spatial domain is, just as electrostatic repulsion flings free charges from the bulk volume to the surface in a typical conductor.
To answer the other question: I think you are misunderstanding the concept of "bare phonon Hamiltonian" and "electron screening". If your question is based on the description in Sec. 7.4.1 of Mahan, "Phonons in Metals", pgs. 482-483, please keep in mind that the model considered therein is that

"the ions are point charges and the electron gas is jellium".

When Mahan says that

"The Hamiltonian of the phonons is first solved without reference to the electrons" (pg. 483, paragraph before Eq.(7.244))

and that

"These phonons are calculated by ignoring electron-electron and electron-phonon interactions. The ion motions are calculated using only the direct ion-ion interaction potential V_{ii}" (pg. 483, paragraph after Eq.(7.244))

he means that in a zero order approximation the phonons and their "bare frequencies" are calculated for ion-ion interaction in a static background of electron gas (or jellium) that does not adjust to the motions of the ions. This is nothing but the Hartree-Fock approximation for the motion of ions or nuclei in the field of the electrons as determined by the instantaneous electronic state - when the electron state is considered as time-independent. As further explained, this is only a convenient first approximation, since in reality the electrons are expected to follow the ions motion rather swiftly, and so their state and the background charge distribution it generates will vary in time. Accounting for such time variation in the electron configuration involves
a) accounting for perturbations in the electron state wrt the electronic zero order approximation of fixed nuclei, leading to electron-electron interaction terms, and
b) accounting for dynamical changes in the ion-ion interaction potential wrt to the nuclear/ionic zero order approximation of fixed background electronic configuration, which reflects in electron-phonon interactions.
As for the acoustic branch of the "bare phonons", it refers to in-phase oscillations of the ions similar to sound waves or charge oscillations in a plasma, wherefrom the analogy. The long wavelength limit $q\rightarrow 0$ corresponds to ions moving coherently in the same direction (whole lattice displacement), and so the oscillation frequency vanishes $\omega_q \rightarrow 0$. The optical branch corresponds to out-of-phase oscillations in which neighboring ions move in opposite/different directions, see here.


TITLE: Let R be a relation and let A = $\cup\cup$R. Then R $\subseteq$ A $\times$ A. proof and notation confusion.
QUESTION [0 upvotes]: I'm currently reading Set Theory a First Course, and one of the lemmas is as follows.
Let R be a relation and let A = $\cup\cup$R. Then R $\subseteq$ A $\times$ A.
I'm having trouble understanding the proof. What is the difference between $\cup$R and $\cup\cup$R? Why is it important that the double union is used? Is this notation the same as R$\cup$R$\cup$R?

REPLY [1 votes]: This is due to simply definition.
Note that a relation is a set of tuples, $\cup A=\{a:a\in S$ for some $S\in A\}$ and a tuple $(a,b)$ is defined as $\{\{a\},\{a,b\}\}$.
Let $A=\cup\cup R$ and $(a,b)\in R$.
Note that, by definition,  $\forall x, x\in\cup\cup R $ iff $x\in S$ for some $S\in \cup R$ iff $x\in S$ and $S\in S'$ for some $S\in S'$ and $S\in R$.
We have $a,b\in \{a,b\}$ and $\{a,b\}\in(a,b)$ for some $\{a,b\}\in(a,b)$ and $(a,b)\in R$. Therefore $a,b\in \cup\cup R=A$, and $(a,b)\in A\times A$.
The proof as above. I can give you some example for you easier to get the idea.
Let $R=\{(a,b)\}$. Then $\cup R=\{\{a\},\{a,b\}\}$ and $\cup\cup R=\{a,b\}$.


TITLE: Convergence of $\int_0^1 x^p ln^q \left(\frac{\ 1}{x}\right)$
QUESTION [0 upvotes]: So far, I determined that the integral converges for every $q>p+1$.
I noticed that for example for the values $p=5, q=3$ the integral still converges. There are some values for which the integral diverges, too.
I have also tried to apply the Dirichlet test and limit tests with various functions.
Any insight on how to determine the exact values of p and q for which the integral diverges/converges will be much appreciated!

REPLY [2 votes]: By setting $x=e^{-t}$ we have:
$$\int_{0}^{1} x^p (-\log x)^q\,dx = \int_{0}^{+\infty} t^q e^{-(p+1)t}\,dt = \frac{\Gamma(q+1)}{(p+1)^{q+1}} $$
as soon as both $p$ and $q$ are greater than $-1$.


TITLE: Is a compact set on a Polish space closed?
QUESTION [0 upvotes]: Proposition: If an exponentially tight familiy $P_\epsilon$ satisfies the LDP (large deviation principle) lower bound for open sets for a rate function I, then I is a good rate function.
The proof now starts with: Let $a>0$ be given and $K_a$ be the corresponding (compact) set from exponential tightness. Note that $K_a^c$ is open,...
My problem is, that I don't see, why we know that $K_a^c$ is open. We are working on a Polish space, and as far as I know, compact doesn't implie closed here, does it?
P.S. LDP lower bound for open sets: For all $G \in X$ open, we have $\liminf_{\epsilon \to 0} \epsilon \ln  \mathbb{P}_\epsilon [G] \geq -\inf_{x \in G} I(x)$  where $I(x)$ is a lower semicontinuous function.
exponential tightness: For all $a>0$ there exists a compact set $K_a$ such that $\limsup_{\epsilon \to 0} \epsilon  \ln \mathbb{P}_\epsilon [K_a^c]<-a$

REPLY [0 votes]: A polish space is metrizable; that is, it is homeomorphic to a metric space. In a metric space the general Heine-Borel Theorem holds, so that a compact set is complete and therefore necessarily closed. Homeomorphisms preserve the properties of compactness and being closed, so the set must also be closed in the original space.


TITLE: What is Meant by a Statistical Decision Problem?
QUESTION [2 upvotes]: I am reading Mathematical Statistics - A Decision Theoretic Approach by Ferguson (Academic Press 1967).
A game in the book is defined as a triple $(\Theta, \mathcal A, L)$, where $L$ is a function from $\Theta\times \mathcal A\to \mathbb R$.
The set $\Theta$ is to be thought of as possible "states of nature" (spooky language), $\mathcal A$ is to be thought of as the set of possible actions one can take, and $L$ is the loss one incurs when an action is taken given a state of nature.
This is formally understand. But then the author, on pg 7, defined a statistical decision problem as:

A statistical decision problem is a game $(\Theta, \mathcal A, L)$ coupled with an experiment involving a random observable $X$ whose distribution $P_\theta$ depends on the state $\theta\in \Theta$ chosen by nature.

It is not clear to me what the author intends to convey.
By an "experiment" I suppose the author means a probability space, and by a random observable I suppose he means a random variable.
But what does it mean to say that the distribution of $X$ depends on the state $\theta$? Does he mean that we actually have a whose set of random variables parameterized by $\Theta$?
Please feel free to add any intuition and elaboration of these concepts. I am a complete beginner here.
Also, if you can suggest a more recent reference for reading this material then that is more than welcome.

REPLY [1 votes]: An experiment is just a random variable $X$ whose distribution $P_\theta$ depends on the state.
You might be able to think of this as a collection of random variables parameterised by $\theta$, but perhaps it would be better to just think of it as just a single random variable whose distribution is potentially different in different states of the world. This interpretation fits better with the intuition I'm about to give below.
What are these definitions meant to formalise?
The idea is that your payoffs $L$ depends jointly on the action you choose in $\mathcal A$ and the state of the world in $\Theta$, and you wish to choose an action to maximise your payoffs (minimise losses). However, the problem is that you don't actually know the state $\theta \in \Theta$. If you did, the problem would be (relatively) trivial. Instead, the only information you have (other than the structure of the game) is the observation of the random variable $X$. Since the distribution of $X$ varies with $\theta$, observing $X$ gives you partial information about the state $\theta$.
Here's a simple example.
Suppose you are at the office, and you're about to head out for lunch, perhaps late into the lunch break. (You're a bit of a workaholic.) However, it may or may not be raining outside. (These are the states of the world.) Thus, you may or may not bring your umbrella. (These are the actions.) You don't like getting wet in your officewear, but you'd also hate to needlessly bring an umbrella. (This describes your loss function.) Unfortunately, your office has no windows, and the Internet is on the fritz, so you can't check the weather online. However, you can look around at your colleagues who have come back from their lunch breaks: some of them may be wet from the rain outside or have umbrellas that are. This gives you partial information about whether it is in fact still raining outside, and you use this information to decide whether to bring your umbrella or not.