Inverse of a particular matrix
 

I have a very special matrix, square n*n, where the lines 0..(n-1) are:
line(i)={1/(i+1), 1/(i+2), ... , 1/(i+n)}

for example, for n==2:
[CODE]
1 1/2
1/2 1/3[/CODE]

for n==3:
[CODE]
1 1/2 1/3
1/2 1/3 1/4
1/3 1/4 1/5[/CODE]

I would like to find the inverse (as a function of "n").

(I would also be interested in *how* to solve the question (not only in the answer), if it's not too complicated)

Thank you!

The above matrix originated from attempting to do a least-squares polynomial fit to a function evaluated over a (large) set of equidistant points. (the order of the matrix corresponds to the degree of the polynomial.)

Have you heard about [URL="https://en.wikipedia.org/wiki/Hilbert_matrix"]Hilbert matrices[/URL]?

[QUOTE=masser;562861]Have you heard about [URL="https://en.wikipedia.org/wiki/Hilbert_matrix"]Hilbert matrices[/URL]?[/QUOTE]

Thanks! I thought that must be some well-known matrix, but I didn't know its name :)

As the wiki article states, those matrices are useful for testing linear algebra solvers; that's how I first learned about them.

In pari/gp:
[CODE]
1 / mathilbert(n)
[/CODE]

Hilbert matrices are notorious for being "numerically bad." It is however ridiculously easy to prove they're "positive definite," hence invertible.

If n is a positive integer, f = f(x) is a polynomial of degree n-1,

f = a[sub]0[/sub] + a[sub]1[/sub]*x + .... + a[sub]n-1[/sub]x[sup]n-1[/sup], we can write [f] as the product of a 1xn and an nx1 matrix (Pari-GP notation),

[f] = [a[sub]0[/sub], a[sub]1[/sub], ..., a[sub]n-1[/sub]]*[1;x;...;x[sup]n-1[/sup]]. Taking the transpose,

[f] = [1,x,...,x[sup]n-1[/sup]]*[a[sub]0[/sub]; a[sub]1[/sub]; ...; a[sub]n-1[/sub]] Multiplying,

[f[sup]2[/sup]] = [a[sub]0[/sub], a[sub]1[/sub], ..., a[sub]n-1[/sub]]*[1;x;...;x[sup]n-1[/sup]]*[1,x,...,x[sup]n-1[/sup]]*[a[sub]0[/sub]; a[sub]1[/sub]; ...; a[sub]n-1[/sub]]

Multiplying the middle two matrices gives the nxn matrix whose i, j entry is x[sup]i+j-2[/sup]. Now, integrate from 0 to 1, and we find:

The (1x1 matrix whose entry is) the integral from 0 to 1 of f[sup]2[/sup](x) dx may thus be expressed

[a[sub]0[/sub], a[sub]1[/sub], ..., a[sub]n-1[/sub]]*H[sub]n[/sub]*[a[sub]0[/sub]; a[sub]1[/sub]; ...; a[sub]n-1[/sub]].

The integral is positive unless f is identically zero, so H[sub]n[/sub] is positive-definite.

All you need, then, :rolleyes: is a set of polynomials of degree 0, 1, 2, ..., n-1 which are orthogonal WRT integration from 0 to 1, (starting, obviously, with the constant polynomial 1). The "standard" set is the "shifted" Legendre polynomials. (The usual Legendre polynomials are orthogonal WRT integration from -1 to 1.)

I want to muck with forum's tex software. (by posting straight from Wiki.)

[QUOTE]The inverse of the Hilbert matrix can be expressed in closed form using binomial coefficients; its entries are[/QUOTE]
[$](H^{-1})_{ij} = (-1)^{i+j}(i + j - 1) \binom {n + i - 1}{n - j} \binom {n + j - 1}{n - i} \binom {i + j - 2}{i - 1}^2[/$]

[QUOTE=Batalov;562885]I want to muck with forum's tex software. (by posting straight from Wiki.)


[$](H^{-1})_{ij} = (-1)^{i+j}(i + j - 1) \binom {n + i - 1}{n - j} \binom {n + j - 1}{n - i} \binom {i + j - 2}{i - 1}^2[/$][/QUOTE]That isn't tex, that is relying on some ugly JS interpreter.

This is tex:
[tex]\((H^{-1})_{ij} = (-1)^{i+j}(i + j - 1) \binom {n + i - 1}{n - j} \binom {n + j - 1}{n - i} \binom {i + j - 2}{i - 1}^2\)[/tex]

At least I can see the tex, although binom isn't defined. :sad:

[QUOTE=retina;562886]That isn't tex, that is relying on some ugly JS interpreter.

This is tex:
[tex]\((H^{-1})_{ij} = (-1)^{i+j}(i + j - 1) {n + i - 1\choose n - j} {n + j - 1\choose n - i} {i + j - 2\choose i - 1}^2\)[/tex]

At least I can see the tex, although binom isn't defined. :sad:[/QUOTE]
Use {n \choose r}.

Thanks
 

[QUOTE=Nick;562887]Use {n \choose r}.[/QUOTE]:tu:

Why? What's wrong with Matjax? The forum uses Matjax.

\[(H^{-1})_{ij} = (-1)^{i+j}(i + j - 1) \binom {n + i - 1}{n - j} \binom {n + j - 1}{n - i} \binom {i + j - 2}{i - 1}^2\]
or inline text: \((H^{-1})_{ij} = (-1)^{i+j}(i + j - 1) \binom {n + i - 1}{n - j} \binom {n + j - 1}{n - i} \binom {i + j - 2}{i - 1}^2\) (just replaced dollars with \( etc. in Serge's formula)

[QUOTE=LaurV;562895]Why? What's wrong with Matjax? The forum uses Matjax.[/QUOTE]Yes, I know.

Mat[b]h[/b]jax is JS, so therefore not happening here.

[QUOTE=retina;562886]This is tex:
[tex]\((H^{-1})_{ij} = (-1)^{i+j}(i + j - 1) \binom {n + i - 1}{n - j} \binom {n + j - 1}{n - i} \binom {i + j - 2}{i - 1}^2\)[/tex][/QUOTE]

It's not TeX, although the command is called that way. From the [URL="http://ctan.math.illinois.edu/support/mimetex/mimetex.html"]CTAN site[/URL] of mimeTeX (which is what is rendering that GIF):
[QUOTE]mimeTeX is an entirely separate little program that doesn't use TeX or its fonts in any way.[/QUOTE]

That's the reason why it looks so bad.

[QUOTE=kruoli;562900]That's the reason why it looks so bad.[/QUOTE]Looks fine to me. Better than the run-on line of text.

This is what I see (with backslash replaced by forward slash to prevent your fancy JS from seeing it):
/((H^{-1})_{ij} = (-1)^{i+j}(i + j - 1) /binom {n + i - 1}{n - j} /binom {n + j - 1}{n - i} /binom {i + j - 2}{i - 1}^2/)