$\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:
- 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$.
- 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:
- All of $X$'s coordinates are distinct.
- All of $Y$'s coordinates are distinct.
- 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.