7
$\begingroup$

This is probably a trivial problem for some people, but I've spent quite some time on it: What is the inverse of the infinite matrix $$ \left[\begin{matrix} 0^0 & 0^1 & 0^2 & 0^3 & \ldots\\ 1^0 & 1^1 & 1^2 & 1^3 & \ldots\\ 2^0 & 2^1 & 2^2 & 2^3 & \ldots\\ 3^0 & 3^1 & 3^2 & 3^3 & \ldots\\ \vdots & \vdots & \vdots & \vdots &\ddots \end{matrix}\right] $$ (Assume that $0^0=1$ for this problem).

I'm not sure if this problem has a solution or is well-defined, but if it has a solution, it would help greatly in a ton of stuff I'm doing (mostly related to generating functions and polynomial approximations). I began by taking the inverse of progressively larger square matricies, but I didn't see any clear pattern.

$\endgroup$
  • 2
    $\begingroup$ You need to specify the domain and range spaces. $\endgroup$ – copper.hat Oct 27 '14 at 3:23
  • 1
    $\begingroup$ @Axoren what does the $n$th row of the product with an infinite column vector look like? $\endgroup$ – Omnomnomnom Oct 27 '14 at 3:28
  • 1
    $\begingroup$ This matrix does not represent a linear transformation with respect to a basis. E.g., applying it to $(1,0,0,0,\ldots)^T$ would give a vector with infinitely many nonzero entries. @Axoren $\endgroup$ – Jonas Meyer Oct 27 '14 at 3:29
  • 1
    $\begingroup$ It certainly makes sense to ask about the limit of the entries of the inverse matrices of the finite upper left portions as the dimension goes to infinity. I think that is what you are asking. The limit may not exist, but it is still a reasonable question (and that is the answer). It may vary strongly (I am guessing) if you take the upper left entry to be $1$ or $0$. It would be good to show the first few inverses you have found. Maybe that would inspire someone. $\endgroup$ – Ross Millikan Oct 27 '14 at 3:43
  • 1
    $\begingroup$ In this example, if the top-left element is $0$, the determinant is $0$. If it is $1$, the determinant is $\infty$. It's easy to see for this example. $\endgroup$ – Axoren Oct 27 '14 at 3:47
4
$\begingroup$

Numerically, we get some very interesting results for the matrix $M_{ij}=(i-1)^{j-1}$ if it is expressed in the Fourier basis with alternating row signs, $$A := \begin{bmatrix}1 \\ & -1 \\ && 1 \\&&& -1 \\ &&&& \ddots \end{bmatrix}\mathcal{F}^{-1} \left[\begin{matrix} 0^0 & 0^1 & 0^2 & 0^3 & \ldots\\ 1^0 & 1^1 & 1^2 & 1^3 & \ldots\\ 2^0 & 2^1 & 2^2 & 2^3 & \ldots\\ 3^0 & 3^1 & 3^2 & 3^3 & \ldots\\ \vdots & \vdots & \vdots & \vdots &\ddots \end{matrix}\right] \mathcal{F}.$$

As the discretization size of $M$ goes up, $M$ becomes extremely ill-conditioned and the entries blow up, so numerical calculations using standard doubles (15 digits of accuracy) will fail when it becomes much larger than 10-by-10. However, there are toolboxes that let you do computation with greater precision, and I used one with 512 digits of accuracy to produce the following images of the real and complex entries of the matrices $A$ up to size 128-by-128:

enter image description here

The color of the $(i,j)$'th pixel in each plot represents $A_{ij}$, the value of the $(i,j)$'th entry of $A$. The first row is the real part of $A$, and the second row is the imaginary part. Red means large positive value, blue means large negative value, and the maximum real value in the plot is shown in the middle. The picture is big but scaled down for display on math.stackexchange - you can open it in a new tab to see it in more detail.

It looks like in this Fourier basis the normalized matrices are converging to an integral operator with a smooth kernel, $$\frac{1}{N}A v \rightarrow \int_0^1 (K(x,y) + iJ(x,y)) v(y) dy,$$

where $K$ and $J$ are the smooth functions in the pictures, and $N$ is some renormalization factor.

Since the kernel is smooth, the action of $A$ will annihilate highly oscillatory functions. Recalling the definition $A = \text{diag}(1,-1,\dots) \mathcal{F}^{-1} M \mathcal{F}$, we see exactly how $M$ is ill-conditioned and what functions are in its numerical null space - functions that are the Fourier transform of a highly oscillatory functions.

Turning this around, there should exist an inverse $A^{-1}$ for the renormalized limit, acting on a space of functions that are sufficiently smooth. Indeed, the following is a plot of the spectrum of the renormalized $A$ in the 128-by-128 case (top right), and it's dominant singular vectors (left, real on top imaginary on bottom):

enter image description here


Here's the Matlab code I used:

%Using Advanpix multiprecision computing toolbox, http://www.advanpix.com/
mp.Digits(512+9);
mp.GuardDigits(9);

jjmin = 2;
jjmax = 7;
jjrange = jjmax - jjmin + 1;

for jj=jjmin:jjmax
    N = 2^jj;

    %Generate original matrix M, where M_nm = (n-1)^(m-1)
    v = mp((0:N-1)'); 
    M = mp(zeros(N,N)); 
    for kk=0:(N-1) 
        M(:,kk+1)=v.^kk; 
    end

    %Generate matrix D F^(-1) M F, where F is the fft, and 
    %D is the diagonal matrix with diagonal [1, -1, 1, -1, ...]
    FMF = mp(zeros(N,N)); 
    for k=1:N 
        ek = mp(zeros(N,1)); 
        ek(k)=1; 
        FMF(:,k) = ifft(ifftshift(M*fft(fftshift(ek)))); 
    end
    for k=1:N 
        FMF(k,:) = (-1)^(k-1)*FMF(k,:); 
    end

    %plot it
    subplot(2, jjrange,jj - jjmin+1)
    imagesc(real(double(FMF)))
    title(['N=', num2str(N)]);

    subplot(2, jjrange, jjrange + jj -jjmin+1)
    imagesc(imag(double(FMF)))
    format short
    title(['max= ',num2str(max(real(FMF(:))),3)])

end

subplot(2,jjrange,1)
ylabel('real(D F^{-1} M F)')

subplot(2,jjrange,jjrange + 1)
ylabel('imag(D F^{-1} M F)')
$\endgroup$
  • 2
    $\begingroup$ The maximum and minimum values of the inverse for the $n$ by $n$ submatrix appear to be growing on the order of $2^n$. Maybe scaling the inverses by a factor of $\frac{1}{2^n}$ would lead to a well-defined limit? $\endgroup$ – Samuel Li Oct 27 '14 at 19:14
0
$\begingroup$

The linear transformations of $\Bbb R^\infty$ Take the form of row-finite matrices (all rows only have finitely many nonzero entries) or column finite matrices (analogously) depending on if you're writing the vectors on the right or left of transformations.

This matrix is neither row nor column finite, so it can't represent a linear transformation, invertible or not.

$\endgroup$
  • $\begingroup$ Can we think of this matrix as a linear transformation from the set of terminating real sequences to $\Bbb R^\infty$? $\endgroup$ – Omnomnomnom Oct 27 '14 at 3:42
  • 1
    $\begingroup$ @rschwieb: It doesn't represent a linear transformation from a vector space to itself with respect to a basis, but it might represent a linear transformation in some other way. E.g., operators on Hilbert space can be represented as matrices wrt an orthonormal basis, and these need not be column finite or row finite. OP should add some context, but your observation doesn't rule out existence of an inverse in some sense. $\endgroup$ – Jonas Meyer Oct 27 '14 at 3:50
  • $\begingroup$ @Omnomnomnom : In that case, $(0,0,0,1\ldots)$ would presumably be a valid input that doesn't result in a valid output, so I think the answer is no. (At least, if I understand what you meant correctly...) $\endgroup$ – rschwieb Oct 27 '14 at 10:18
  • $\begingroup$ By "terminating," I meant containing finitely many non-zero entries $\endgroup$ – Omnomnomnom Oct 27 '14 at 11:07
  • $\begingroup$ @Omnomnomnom : ok , that's what I thought. My example still stands, right? (I had meant for that to be the only 1 in a string of zeros, but I wasn't very clear about it...) $\endgroup$ – rschwieb Oct 27 '14 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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