Rank of Matrix Multiplication tensor $\langle1,n,1\rangle$

66 Views Asked by At

$\newcommand{\rank}{\operatorname{rank}}$I am reading through Belzer's Fast Matrix Multiplication, available here.

I want to prove tjat $$\rank(t)=\rank(\langle1,n,1\rangle)=n$$

In "usual tensor notation", $t$ is represented as $t\in F^{(1\cdot n)\times (n\cdot 1) \times (1\cdot1)} = F^{n\times n\times 1} $.

I thought about proving it as following:

  1. Transferring the discussion into a Bi-linear function $B:F^{1\times n} \times F^{n\times 1} \rightarrow F^{1\times 1}$. I know that $\rank(B)=\rank(t)$. Then, I want to show that $\rank(B)=n$.
  2. I show the required equality by two directions: The first is $\rank(B) \leq n$ and the second is $\rank(B) \geq n$.

Direction 1

By the definition of the rank of a Bi-linear function, it requires at most $n$ products. This gives me $\rank(t) \leq n$.

Direction 2

I thought about looking at one kind of Bi-linear function that fits $B$, namely dot-product. Then, by taking $X\in F^{1\times n}, Y\in F^{n\times 1}$ such that:

  1. All of $X$'s coordinates are distinct.
  2. All of $Y$'s coordinates are distinct.
  3. Both $X,Y$ share no coordinates.

And then claim that this bi-linear function requires calculation of all $x_i\cdot y_i$, for $1\leq i\leq n$. However, this part of the proof seems a bit shaky.

Any suggestions or feedback will be much appreciated.