Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let's call an $\ell^2$-function $\mathbb{N} \times \mathbb{N} \to \mathbb{C}$ algebraic if it is in the image of the natural algebra homomorphism $\ell^2(\mathbb{N}) \otimes \ell^2(\mathbb{N}) \to \ell^2(\mathbb{N} \times \mathbb{N})$, where on the left hand side we consider the usual, non-completed tensor product. In other words, $f(m,n)$ is algebraic iff it may be written as $\sum_{i=1}^{k} g_i(m) h_i(n)$ for some $k \in \mathbb{N}$ and $\ell^2$-functions $g_i,h_i$. Probably there are abstract reasons for the existence of non-algebraic functions. But I would like to know an explicit example of an $\ell^2$-function together with a concise and complete proof that it is not algebraic. For example:

Question. Can you give a proof that the $\ell^2$-function $(n,m) \mapsto \dfrac{1}{2^{n \cdot m}}$ is not algebraic?

share|cite|improve this question
Are you specifically asking about $1/2^{nm}$, or just looking for any example? – Colin McQuillan Dec 21 '11 at 15:15
Basically I'm just looking for some example. But $2^{-nm}$ would be one of my favorites. Sorry but I don't understand your answer so far ... – Martin Brandenburg Jan 9 '12 at 9:35
up vote 3 down vote accepted

Colin McQuillan's answer is terse, correct, but difficult to understand for typographical reasons: There should be some letters below the arrows.

I shall elaborate using the function $f(m,n):=2^{-mn}$ suggested by the OP as example. For any given $p\in{\mathbb N}$ the ($p\times p)$-matrix $$F_p:=\bigl [f(m,n)\bigr]_{1\leq m\leq p, \ 1\leq n\leq p}$$ is essentially a Vandermonde matrix and therefore has rank $p$, whatever $p$.

On the other hand, for any two functions $g,\ h\in\ell^2$ the tensor product $t:=g\otimes h$ is defined by $t(m,n):=g(m)\ h(n)$. The corresponding matrix $$T_p:=\bigl [t(m,n)\bigr]_{1\leq m\leq p, \ 1\leq n\leq p} =\bigl [g(m)\ h(n)\bigr]_{1\leq m\leq p, \ 1\leq n\leq p}$$ has rank $\ (\leq )\ 1$, whatever $p$, since all its rows are multiples of the vector $(h(1),h(2),\ldots,h(p))$. If we are given $k\geq 1$ such pairs $g_i$, $h_i$ and put $q:=\sum_{i=1}^k g_i\otimes h_i$ then the matrix $$Q_p:=\bigl [q(m,n)\bigr]_{1\leq m\leq p, \ 1\leq n\leq p}$$ is a sum of $k$ rank-one matrices and therefore has rank $\ \leq k$, whatever $p$. It follows that $Q_p\ne F_p$ as soon as $p>k$; whence the function $f$ of the example is not "algebraic" as defined by the OP.

share|cite|improve this answer
Thank you for this detailed explanation. – Martin Brandenburg Feb 15 '12 at 14:36

An algebraic function has bounded rank (either as a tensor, or in this case just as a matrix). So let $f(n,m)$ be $1/2^n$ if $n=m$ and zero otherwise. For all $p$ the composition $\{1,\cdots,p\}\times\{1,\cdots,p\}\to \mathbb{N}\times \mathbb{N}\to \mathbb{C}$ is a $p\times p$ matrix of full rank. If $f$ is algebraic then this matrix is just $\sum_{i=1}^k g_i(m)h_i(n)$ which has rank at most $k$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.