Bonus homework 1

This is meant to have you use whatever means available to solve a concrete matrix-theoretic problem relating to material you will have learned recently. I'll state the problem first, and then we'll get to how you might go about it.

Let $n\in \mathbb{Z}_{>0}$ be a positive integer, and denote by $A_n$ the $n\times n$ matrix whose entry in row $i$ and column $j$ is $\max(i,j)$. So for instance:

In [1]:
from sympy import *
init_printing(use_latex='mathjax')
In [3]:
f = lambda i,j: max(i+1,j+1)
In [4]:
A_5 = Matrix(5,5,f)
In [5]:
A_5
Out[5]:
$\displaystyle \left[\begin{matrix}1 & 2 & 3 & 4 & 5\\2 & 2 & 3 & 4 & 5\\3 & 3 & 3 & 4 & 5\\4 & 4 & 4 & 4 & 5\\5 & 5 & 5 & 5 & 5\end{matrix}\right]$

Note how I had to ask Python to take the maximum of $i+1$ and $j+1$ instead of $i$ and $j$, because as mentioned before its indexing starts at $0$. So what for us is entry $(i,j)$ in a matrix, for Python is $(i-1,j-1)$.


OK, so here's what you're supposed to do: take the matrix $A_{2020}$ (that's size $2020\times 2020$, so it's pretty large..) and tell me what the entry is in the last row and last column of its inverse $(A_{2020})^{-1}$.

Remember from our textbook's section 2.2 that the inverse $A^{-1}$ of an $n\times n$ matrix $A$ is another $n\times n$ matrix which gives you back the identity when you multiply both on the left and right:

$$ A \cdot A^{-1} = A^{-1} \cdot A = I_n, $$

where $I_n$ is the matrix with ones down the diagonal and zeros elsewhere (what I referred to as the {\it identity matrix}).

How might you go about this? I don't think actually computing the inverse $A_{2020}^{-1}$ is an option: on my computer(s) simply trying to find the inverse with, say, Sympy's A.inv() method chokes on matrices as small as $20\times 20$ (let alone $2020$!).

There's also NumPy and its numpy.linalg.inv() function (which you can apply to your matrix after you've converted it to a NumPy array), but that won't help you: while it works quickly on larger-sized matrices, it's purely numerical and NumPy will start to make rounding errors very fast.

So I suggest a combination of methods:

  • examine a few small cases with Python or by hand (your computer will have no trouble inverting $A_n$ for $n\le 10$ or so);
  • try to guess the general form of the inverse $A_n^{-1}$, for arbitrary $n$; that'll just be pattern recognition on your part;
  • try to show, having made the guess, that you did indeed guess the right answer.

For your work to qualify as a valid solution you need to

  • tell me the correct answer (the entry of the matrix $A_{2020}^{-1}$ in position $(2020,2020)$)
  • tell me how you got it, as you would in any homework assignment: lay out the pure-math solution or, if you managed to get a computer to tell you the answer, tell me how in enough detail that I can reproduce those steps.

In short: show me your work.

The point of this is to have you do some exploratory work, learning some new material along the way spurred on by a specific problem: this is how problem-solving works! For instance, what's that lambda thing I used in the Python code above? If you're not familiar with the concept, go read about it, or, for that matter, about the abstract mathematical concept this construct is based on.

So throw anything you can at it: Python, plain pure math, your google-fu, whatever.

In [ ]: