Tensors And Matrices

Complexity of rank of 3-tensorShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Complexity of rank of 3-tensorHastad 1990: Tensor rank is NP-complete for any finite field andNP-hard for rational numbersShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Complexity of rank of 3-tensorHastad 1990: Tensor rank is NP-complete for any finite field andNP-hard for rational numbersPRF: 3-sat with n variables m clausessatisfiable iff rank T 4n 2m, T F(2n 3m) (3n) (3n m) )otherwise rank is largerShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank: F R, CShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank: F R, CRr (m, n, l) Fm n l : all tensors of rank rShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank: F R, CRr (m, n, l) Fm n l : all tensors of rank rRr (m, n, l) not closed variety for r 2Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank: F R, CRr (m, n, l) Fm n l : all tensors of rank rRr (m, n, l) not closed variety for r 2Border rank of T the minimum k s.t. T is a limit of Tj , j N, rank Tj k .Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank: F R, CRr (m, n, l) Fm n l : all tensors of rank rRr (m, n, l) not closed variety for r 2Border rank of T the minimum k s.t. T is a limit of Tj , j N, rank Tj k .generic rank border rank typical rank of Fm n l : grankF (m, n, l) the rank of a random tensor T Fm n lShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank of Fm n lTHM: grankC (m, n, l) min(l, mn) for (m 1)(n 1) 1 l.Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank of Fm n lTHM: grankC (m, n, l) min(l, mn) for (m 1)(n 1) 1 l.Reason: For l (m 1)(n 1) 1 a generic subspace of matrices ofdimension l in Cm n intersect the variety of rank one matrices in Cm nat least at l lines which contain l linearly independent matricesShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank of Fm n lTHM: grankC (m, n, l) min(l, mn) for (m 1)(n 1) 1 l.Reason: For l (m 1)(n 1) 1 a generic subspace of matrices ofdimension l in Cm n intersect the variety of rank one matrices in Cm nat least at l lines which contain l linearly independent matricesCOR: grankC (2, n, l) min(l, 2n) for 2 n lShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank of Fm n lTHM: grankC (m, n, l) min(l, mn) for (m 1)(n 1) 1 l.Reason: For l (m 1)(n 1) 1 a generic subspace of matrices ofdimension l in Cm n intersect the variety of rank one matrices in Cm nat least at l lines which contain l linearly independent matricesCOR: grankC (2, n, l) min(l, 2n) for 2 n lDimension count for F C and 2 m n l (m 1)(n 1) 1:Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank of Fm n lTHM: grankC (m, n, l) min(l, mn) for (m 1)(n 1) 1 l.Reason: For l (m 1)(n 1) 1 a generic subspace of matrices ofdimension l in Cm n intersect the variety of rank one matrices in Cm nat least at l lines which contain l linearly independent matricesCOR: grankC (2, n, l) min(l, 2n) for 2 n lDimension count for F C and 2 m n l (m 1)(n 1) 1:fr : (Cm Cn Cl )r Cm n l , x y z (ax) (by) ((ab) 1 z)Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank of Fm n lTHM: grankC (m, n, l) min(l, mn) for (m 1)(n 1) 1 l.Reason: For l (m 1)(n 1) 1 a generic subspace of matrices ofdimension l in Cm n intersect the variety of rank one matrices in Cm nat least at l lines which contain l linearly independent matricesCOR: grankC (2, n, l) min(l, 2n) for 2 n lDimension count for F C and 2 m n l (m 1)(n 1) 1:fr : (Cm Cn Cl )r Cm n l , x y z (ax) (by) ((ab) 1 z)mnlgrankC (m, n, l)(m n l 2) mnl grankC (m, n, l) d (m n l 2)eShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank of Fm n lTHM: grankC (m, n, l) min(l, mn) for (m 1)(n 1) 1 l.Reason: For l (m 1)(n 1) 1 a generic subspace of matrices ofdimension l in Cm n intersect the variety of rank one matrices in Cm nat least at l lines which contain l linearly independent matricesCOR: grankC (2, n, l) min(l, 2n) for 2 n lDimension count for F C and 2 m n l (m 1)(n 1) 1:fr : (Cm Cn Cl )r Cm n l , x y z (ax) (by) ((ab) 1 z)mnlgrankC (m, n, l)(m n l 2) mnl grankC (m, n, l) d (m n l 2)emnlConjecture grankC (m, n, l) d (m n l 2)efor 2 m n l (m 1)(n 1) and (3, n, l) 6 (3, 2p 1, 2p 1)Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank of Fm n lTHM: grankC (m, n, l) min(l, mn) for (m 1)(n 1) 1 l.Reason: For l (m 1)(n 1) 1 a generic subspace of matrices ofdimension l in Cm n intersect the variety of rank one matrices in Cm nat least at l lines which contain l linearly independent matricesCOR: grankC (2, n, l) min(l, 2n) for 2 n lDimension count for F C and 2 m n l (m 1)(n 1) 1:fr : (Cm Cn Cl )r Cm n l , x y z (ax) (by) ((ab) 1 z)mnlgrankC (m, n, l)(m n l 2) mnl grankC (m, n, l) d (m n l 2)emnlConjecture grankC (m, n, l) d (m n l 2)efor 2 m n l (m 1)(n 1) and (3, n, l) 6 (3, 2p 1, 2p 1)2Fact: grankC (3, 2p 1, 2p 1) d 3(2p 1)4p 3 e 1Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Bilinear maps and product of matricesbilinear map: φ : U V WShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Bilinear maps and product of matricesbilinear map: φ : U V W[u1 , . . . , um ], [v1 , . . . , vn ], [w1 , . . . , wl ] bases in U, V, WShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Bilinear maps and product of matricesbilinear map: φ : U V W[u1 , . . . , um ], [v1 , . . . , vn ], [w1 , . . . , wl ] bases in U, V, Wφ(ui , vj ) Pk 1 ti,j,k wk ,Shmuel Friedland Univ. Illinois at Chicago ()T : [ti,j,k ] Fm n lTensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Bilinear maps and product of matricesbilinear map: φ : U V W[u1 , . . . , um ], [v1 , . . . , vn ], [w1 , . . . , wl ] bases in U, V, Wφ(ui , vj ) T PrPa 1 xak 1 ti,j,k wk ,T : [ti,j,k ] Fm n l ya za , r rank TShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Bilinear maps and product of matricesbilinear map: φ : U V W[u1 , . . . , um ], [v1 , . . . , vn ], [w1 , . . . , wl ] bases in U, V, Wφ(ui , vj ) T PPra 1 xaφ(c, d) Prk 1 ti,j,k wk ,T : [ti,j,k ] Fm n l ya za , r rank Ta 1 (c x)(d y)z ,aShmuel Friedland Univ. Illinois at Chicago ()c Pmi 1 ci ui , dTensors and Matrices Pnj 1 dj vjWest Canada Linear Algebra Meeting, May 7-9/ 24

Bilinear maps and product of matricesbilinear map: φ : U V W[u1 , . . . , um ], [v1 , . . . , vn ], [w1 , . . . , wl ] bases in U, V, Wφ(ui , vj ) T PrPa 1 xak 1 ti,j,k wk ,T : [ti,j,k ] Fm n l ya za , r rank TPPPnφ(c, d) ra 1 (c x)(d y)za , c mi 1 ci ui , d j 1 dj vjComplexity: r -productsShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Bilinear maps and product of matricesbilinear map: φ : U V W[u1 , . . . , um ], [v1 , . . . , vn ], [w1 , . . . , wl ] bases in U, V, Wφ(ui , vj ) T PrPa 1 xak 1 ti,j,k wk ,T : [ti,j,k ] Fm n l ya za , r rank TPPPnφ(c, d) ra 1 (c x)(d y)za , c mi 1 ci ui , d j 1 dj vjComplexity: r -productsMatrix product τ : FM N FN L FM L , (A, B) 7 ABShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Bilinear maps and product of matricesbilinear map: φ : U V W[u1 , . . . , um ], [v1 , . . . , vn ], [w1 , . . . , wl ] bases in U, V, Wφ(ui , vj ) T PrPa 1 xak 1 ti,j,k wk ,T : [ti,j,k ] Fm n l ya za , r rank TPPPnφ(c, d) ra 1 (c x)(d y)za , c mi 1 ci ui , d j 1 dj vjComplexity: r -productsMatrix product τ : FM N FN L FM L , (A, B) 7 AB4 4 4M N L 2, grankC (4, 4, 4) d 4 4 4 2e d6.4e 7Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Bilinear maps and product of matricesbilinear map: φ : U V W[u1 , . . . , um ], [v1 , . . . , vn ], [w1 , . . . , wl ] bases in U, V, Wφ(ui , vj ) T PrPa 1 xak 1 ti,j,k wk ,T : [ti,j,k ] Fm n l ya za , r rank TPPPnφ(c, d) ra 1 (c x)(d y)za , c mi 1 ci ui , d j 1 dj vjComplexity: r -productsMatrix product τ : FM N FN L FM L , (A, B) 7 AB4 4 4M N L 2, grankC (4, 4, 4) d 4 4 4 2e d6.4e 7Product of two 2 2 matrices is done by 7 multiplicationsShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Known cases of rank conjectureShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Known cases of rank conjecture2212pgrank(3, 2p, 2p) d 4p 1e and grank(3, 2p 1, 2p 1) d 3(2p 1)4p 1 e 1Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Known cases of rank conjecture2212pgrank(3, 2p, 2p) d 4p 1e and grank(3, 2p 1, 2p 1) d 3(2p 1)4p 1 e 1(n, n, n 2) if n 6 2 (mod 3),Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Known cases of rank conjecture2212pgrank(3, 2p, 2p) d 4p 1e and grank(3, 2p 1, 2p 1) d 3(2p 1)4p 1 e 1(n, n, n 2) if n 6 2 (mod 3),(n 1, n, n) if n 0 (mod 3),Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Known cases of rank conjecture2212pgrank(3, 2p, 2p) d 4p 1e and grank(3, 2p 1, 2p 1) d 3(2p 1)4p 1 e 1(n, n, n 2) if n 6 2 (mod 3),(n 1, n, n) if n 0 (mod 3),(4, m, m) if m 4,Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Known cases of rank conjecture2212pgrank(3, 2p, 2p) d 4p 1e and grank(3, 2p 1, 2p 1) d 3(2p 1)4p 1 e 1(n, n, n 2) if n 6 2 (mod 3),(n 1, n, n) if n 0 (mod 3),(4, m, m) if m 4,(n, n, n) if n 4Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Known cases of rank conjecture2212pgrank(3, 2p, 2p) d 4p 1e and grank(3, 2p 1, 2p 1) d 3(2p 1)4p 1 e 1(n, n, n 2) if n 6 2 (mod 3),(n 1, n, n) if n 0 (mod 3),(4, m, m) if m 4,(n, n, n) if n 42lp(l, 2p, 2q) if l 2p 2q and and l 2p 2q 2is integerShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Known cases of rank conjecture2212pgrank(3, 2p, 2p) d 4p 1e and grank(3, 2p 1, 2p 1) d 3(2p 1)4p 1 e 1(n, n, n 2) if n 6 2 (mod 3),(n 1, n, n) if n 0 (mod 3),(4, m, m) if m 4,(n, n, n) if n 42lp(l, 2p, 2q) if l 2p 2q and and l 2p 2q 2is integerEasy to compute grankC (m, n, l):Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Known cases of rank conjecture2212pgrank(3, 2p, 2p) d 4p 1e and grank(3, 2p 1, 2p 1) d 3(2p 1)4p 1 e 1(n, n, n 2) if n 6 2 (mod 3),(n 1, n, n) if n 0 (mod 3),(4, m, m) if m 4,(n, n, n) if n 42lp(l, 2p, 2q) if l 2p 2q and and l 2p 2q 2is integerEasy to compute grankC (m, n, l):Pick at random wr : (x1 , y1 , z1 , . . . , xr , yr , zr ) (Rm Rn Rl )rShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Known cases of rank conjecture2212pgrank(3, 2p, 2p) d 4p 1e and grank(3, 2p 1, 2p 1) d 3(2p 1)4p 1 e 1(n, n, n 2) if n 6 2 (mod 3),(n 1, n, n) if n 0 (mod 3),(4, m, m) if m 4,(n, n, n) if n 42lp(l, 2p, 2q) if l 2p 2q and and l 2p 2q 2is integerEasy to compute grankC (m, n, l):Pick at random wr : (x1 , y1 , z1 , . . . , xr , yr , zr ) (Rm Rn Rl )rmnle s.t. rank J(fr )(wr ) mnlThe minimal r d (m n l 2)is grankC (m, n, l) (Terracini Lemma 1915)Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Known cases of rank conjecture2212pgrank(3, 2p, 2p) d 4p 1e and grank(3, 2p 1, 2p 1) d 3(2p 1)4p 1 e 1(n, n, n 2) if n 6 2 (mod 3),(n 1, n, n) if n 0 (mod 3),(4, m, m) if m 4,(n, n, n) if n 42lp(l, 2p, 2q) if l 2p 2q and and l 2p 2q 2is integerEasy to compute grankC (m, n, l):Pick at random wr : (x1 , y1 , z1 , . . . , xr , yr , zr ) (Rm Rn Rl )rmnle s.t. rank J(fr )(wr ) mnlThe minimal r d (m n l 2)is grankC (m, n, l) (Terracini Lemma 1915)Avoid round-off error:wr (Zm Zn Zl )r find rank J(fr )(wr ) exact arithmeticShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Known cases of rank conjecture2212pgrank(3, 2p, 2p) d 4p 1e and grank(3, 2p 1, 2p 1) d 3(2p 1)4p 1 e 1(n, n, n 2) if n 6 2 (mod 3),(n 1, n, n) if n 0 (mod 3),(4, m, m) if m 4,(n, n, n) if n 42lp(l, 2p, 2q) if l 2p 2q and and l 2p 2q 2is integerEasy to compute grankC (m, n, l):Pick at random wr : (x1 , y1 , z1 , . . . , xr , yr , zr ) (Rm Rn Rl )rmnle s.t. rank J(fr )(wr ) mnlThe minimal r d (m n l 2)is grankC (m, n, l) (Terracini Lemma 1915)Avoid round-off error:wr (Zm Zn Zl )r find rank J(fr )(wr ) exact arithmeticI checked the conjecture up to m, n, l 14Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank III - the real caseShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank III - the real caseFor mn l grankR (m, n, l) mn.Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank III - the real caseFor mn l grankR (m, n, l) mn.For 2 m n l mn 1, there exist V1 , . . . , Vc(m,n,l) Rm n lpairwise distinct open connected semi-algebraic sets s.t.Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank III - the real caseFor mn l grankR (m, n, l) mn.For 2 m n l mn 1, there exist V1 , . . . , Vc(m,n,l) Rm n lpairwise distinct open connected semi-algebraic sets s.t.c(m,n,l)Closure( i 1) Rm n lShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank III - the real caseFor mn l grankR (m, n, l) mn.For 2 m n l mn 1, there exist V1 , . . . , Vc(m,n,l) Rm n lpairwise distinct open connected semi-algebraic sets s.t.c(m,n,l)Closure( i 1) Rm n lrank T grankC (m, n, l) for each T V1Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank III - the real caseFor mn l grankR (m, n, l) mn.For 2 m n l mn 1, there exist V1 , . . . , Vc(m,n,l) Rm n lpairwise distinct open connected semi-algebraic sets s.t.c(m,n,l)Closure( i 1) Rm n lrank T grankC (m, n, l) for each T V1rank T ρi for each T ViShmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank III - the real caseFor mn l grankR (m, n, l) mn.For 2 m n l mn 1, there exist V1 , . . . , Vc(m,n,l) Rm n lpairwise distinct open connected semi-algebraic sets s.t.c(m,n,l)Closure( i 1) Rm n lrank T grankC (m, n, l) for each T V1rank T ρi for each T Viρi grankC (m, n, l) for i 2, . . . , c(m, n, l)Shmuel Friedland Univ. Illinois at Chicago ()Tensors and MatricesWest Canada Linear Algebra Meeting, May 7-9/ 24

Generic rank III - the real caseFor mn l grankR (m, n, l) mn.For 2 m n l mn 1, there exist V1 , . . . , Vc(m,n,l) Rm n lpairwise distinct open connected semi-algebraic sets s.t.c(m,n,l)Closure( i 1) Rm n lrank T grankC (m, n, l) for each T

Overview Ranks of3-tensors 1 Basic facts. 2 Complexity. 3 Matrix multiplication 4 Results and conjectures Approximations of tensors 1 Rank one approximation. 2 Perron-Frobenius theorem 3 Rank (R1;R2;R3) approximations 4 CUR approximations Diagonal scaling of nonnegative tensors to tensors with given rows, columns and depth sums