How to prove that this matrix is invertible by only elimination? Hoffman & Kunze exercise 1.6.12

Question

Hoffman & Kunze exercise 1.6.12 wants a proof that this matrix is invertible

$$\begin{pmatrix} 1 & \frac{1}{2} & \frac{1}{3} & \dots & \frac{1}{n} \\\\ \frac{1}{2} & \frac{1}{3} & \frac{1}{4} & \dots & \frac{1}{n+1} \\\\ \vdots & \vdots & \vdots & \ddots & \vdots \\\\ \frac{1}{n} & \frac{1}{n+1} & \frac{1}{n+2} & \dots & \frac{1}{2n-1} \end{pmatrix}$$

The book only uses elimination method in chapter 1 to find an inverse to a matrix

I tried to use induction and to define a sequence of matrices $A_n$ such that

$$ A_n:=\begin{pmatrix} 1 & \frac{1}{2} & \frac{1}{3} & \dots & \frac{1}{n} \\\\ \frac{1}{2} & \frac{1}{3} & \frac{1}{4} & \dots & \frac{1}{n+1} \\\\ \vdots & \vdots & \vdots & \ddots & \vdots \\\\ \frac{1}{n} & \frac{1}{n+1} & \frac{1}{n+2} & \dots & \frac{1}{2n-1} \end{pmatrix}$$

and assume that $A_n$ is invertible and prove that $A_{n+1}$ is also invertible and apply all the elementary row operations to make the $A_n$ that is inside $A_{n+1}$ be reduced to $I$ , but the last column of $A_{n+1}$ will be very difficult to calculate.

Answer 1

The answer below is incorrect: the transformation described takes $A_n$ and replaces the first column with $(1,0,\dots,0)$; it does not result in the desired recursive approach.

---

There is an excerpt from the end of section 1.6 that seems very relevant here:

It must have occurred to the reader that we have carried on a lengthy discussion of the rows of matrices and have said little about the columns. We focused our attention on the rows because this seemed more natural from the point of view of linear equations. Since there is obviously nothing sacred about rows, the discussion in the last sections could have been carried on using columns rather than rows. If one defines an elementary column operation and column-equivalence in a manner analogous to that of elementary row operation and row-equivalence, it is clear that each $m \times n$ matrix will be column-equivalent to a "column-reduced echelon" matrix. Also, each elementary column operation will be of the form $A \to AE$, where $E$ is an $n \times n$ elementary matrix, and so on.

With that, we can arrive at a sort of generalization of Theorem 12 from that section: $A$ is invertible if and only if it can be brought to the identity matrix via a combination of row operations and column operations. Also, per Theorem 12, this means that if it is possible to bring a matrix to the identity with a combination of row and column operations, then it is in principle possible to do so using row operations alone.

With that in mind we apply the following operations. First, subtract $(1/i)$ times row 1 from row $i$ for each $i = 2,3,\dots,n$. Note that $$ \frac 1{i+j - 1} - \frac 1i\cdot \frac 1{j} = \\ \frac{ij - (i + j - 1)}{ij(i + j - 1)} = \\ \frac{(i - 1)(j - 1)}{ij(i+j-1)} $$ Thus, for each $i > 1$, the $i,j$ entry is $\frac{(i - 1)(j - 1)}{ij(i+j-1)}$. Note in particular that the first entry of each row (i.e. the $j = 1$ entry for each $i$) is zero.

Next, for each $i > 1$, multiply the $i$th row by $\frac i{i-1}$. Similarly, for each $j > 1$, multiply the $j$th column by $\frac j{j-1}$. For each $i > 1$, we still have zeros in the first column, and for $j > 1$ the entries are now $\frac{1}{i + j - 1}$. In other words, with a combination of row and column combinations, we have made the transition $$ A_n \to \pmatrix{1 & *\\0 & A_{n-1}}, $$ where in the above $*$ denotes a row of entries (that we don't care about) and $0$ denotes a column of zeroes. Conclude that the first matrix is invertible if and only if the second is invertible.

With that, we can build an inductive proof: suppose that $A_{n-1}$ is invertible. Then, it is possible to reduce $A_{n-1}$ to an identity matrix with row operations. Thus, we can show that the matrix $\pmatrix{1 & *\\0 & A_{n-1}}$ is invertible by bringing it to the identity matrix with the transitions $$ \pmatrix{1 & *\\0 & A_{n-1}} \to \pmatrix{1 & *\\0 & I_{n-1}} \to \pmatrix{1 & 0\\0 & I_{n-1}}. $$ So, the matrix $\pmatrix{1 & *\\0 & A_{n-1}}$ is invertible, which means that $A_n$ is invertible.

So, $A_{n-1}$ being invertible implies that $A_n$ is invertible. Inductively, we can conclude that $A_n$ is invertible for all $n$.