Editing Matrix norm (section)

==Cut norms==
Another source of inspiration for matrix norms arises from considering a matrix as the [[adjacency matrix]] of a [[Weighted graph|weighted]], [[directed graph]].<ref name="FK">{{Cite journal|last1=Frieze| first1=Alan| last2=Kannan|first2=Ravi| date=1999-02-01|title=Quick Approximation to Matrices and Applications| url=https://doi.org/10.1007/s004930050052| journal=Combinatorica|language=en| volume=19 |issue=2 |pages=175–220 |doi=10.1007/s004930050052 |s2cid=15231198 |issn=1439-6912|url-access=subscription}}</ref>  The so-called "cut norm" measures how close the associated graph is to being [[bipartite graph|bipartite]]:
<math display="block">\|A\|_{\Box}=\max_{S\subseteq[n], T\subseteq[m]}{\left|\sum_{s\in S,t\in T}{A_{t,s}}\right|}</math> 
where {{math|''A'' &isin; ''K''<sup>''m''×''n''</sup>}}.<ref name="FK" /><ref name="LNGL">{{Cite book| last=Lovász László|title=Large Networks and Graph Limits |publisher=American Mathematical Society|year=2012| isbn=978-0-8218-9085-1 | series=AMS Colloquium Publications|volume=60| location=Providence, RI|pages=127–131 |chapter=The cut distance|author-link=László Lovász}}  Note that Lovász rescales {{math|‖''A''‖<sub>□</sub>}} to lie in {{closed-closed|0, 1}}.</ref><ref name="AN">{{Cite book|last1=Alon |first1=Noga |author-link=Noga Alon| last2=Naor| first2=Assaf|title=Proceedings of the thirty-sixth annual ACM symposium on Theory of computing |chapter=Approximating the cut-norm via Grothendieck's inequality | date=2004-06-13| chapter-url=https://doi.org/10.1145/1007352.1007371 | series=STOC '04 |location=Chicago, IL, USA | publisher=Association for Computing Machinery| pages=72–80| doi=10.1145/1007352.1007371 | isbn=978-1-58113-852-8 |s2cid=1667427}}</ref>  Equivalent definitions (up to a constant factor) impose the conditions {{math|2{{abs|''S''}} > ''n'' &amp; 2{{abs|''T''}} > ''m''}}; {{math|1=''S'' = ''T''}}; or {{math|1=''S'' &cap; ''T'' = &emptyset;}}.<ref name="LNGL" />

The cut-norm is equivalent to the induced operator norm {{math|‖·‖<sub>&infin;→1</sub>}}, which is itself equivalent to another norm, called the [[Grothendieck inequality|Grothendieck]] norm.<ref name="AN" />

To define the Grothendieck norm, first note that a linear operator {{Math|''K''<sup>1</sup> → ''K''<sup>1</sup>}} is just a scalar, and thus extends to a linear operator on any {{Math|''K<sup>k</sup>'' → ''K<sup>k</sup>''}}.  Moreover, given any choice of basis for {{Math|''K<sup>n</sup>''}} and {{Math|''K<sup>m</sup>''}}, any linear operator {{Math|''K<sup>n</sup>'' → ''K<sup>m</sup>''}} extends to a linear operator {{Math|(''K''<sup>''k''</sup>)<sup>''n''</sup> → (''K''<sup>''k''</sup>)<sup>''m''</sup>}}, by letting each matrix element on elements of {{Math|''K<sup>k</sup>''}} via scalar multiplication.  The Grothendieck norm is the norm of that extended operator; in symbols:<ref name="AN" />
<math display="block">\|A\|_{G,k}=\sup_{\text{each } u_j, v_j\in K^k; \|u_j\| = \|v_j\| = 1}{\sum_{j \in [n], \ell \in [m]}{(u_j\cdot v_j) A_{\ell,j}}}</math>

The Grothendieck norm depends on choice of basis (usually taken to be the [[standard basis]]) and {{mvar|k}}.