Prove that $ Cond_{\infty} (A) \geq C n^2$ for some positive constant C independent of n. $A \in \mathbb{R}^{n \times n}$ so that:
$$a_{ij} = \begin{cases} 1 & \text{if } i = 1 \text{ or } j = 1 \\ \frac{1}{i} & \text{if } i = j \\ 0 &\text{Otherwise} \end{cases}$$
For that I'm using that $ Cond_{\infty} (A) \geq \frac{|| A||_{\infty}}{|| A - B||_{\infty}} $ for any singular matrix B. It's easy to see that $|| A||_\infty = n $ since the sum of the first row is always bigger than the sum of the others. So now I have to find a suitable matrix $B$ so that $||A - B||_\infty = (Cn)^{-1}$ or something similar to that.
I've tried a number of different matrixes and tried to solve it for $n=4$ but none of them really work. The closest result I got was $||A - B||_\infty = \frac{1 + n}{n}$ with
$$b_{ij} = \begin{cases} a_{ij} & \text{if } i \neq n \\ 0 &\text{if } i = n \end{cases}$$
In that case the only non zero elements of $A - B$ are $(a-b)_{n1} = 1$ and $(a-b)_{nn} = \frac{1}{n}$ so $\frac{||A||_{\infty}}{||A-B||_{\infty}} =\frac{n^2}{n + 1}$ but I'm unable to find a lower bound for that independent of n.
Any help would be greatly appreciated.
You already showed that $\|A\|_{\infty} = n$, so now we just need to get a lower bound on $\|A^{-1}\|_{\infty}$ and use $\text{Cond}_{\infty}(A) = \|A\|_{\infty}\|A^{-1}\|_{\infty}$ to get a lower bound on $\text{Cond}_{\infty}(A)$.
We can partition $$A = \begin{bmatrix}1 & \vec{1}^T \\ \vec{1} & D^{-1}\end{bmatrix}$$ where $\vec{1}$ is a column vector of $n-1$ ones and $D = \text{diag}(2,3,\ldots,n)$.
Now, use the Block Matrix Inversion Formula to get
$$A^{-1} = \begin{bmatrix}a & -a\vec{1}^TD \\ -D\vec{1}a & D+D\vec{1}a\vec{1}^TD\end{bmatrix}$$ where $$a = (1-\vec{1}^TD\vec{1})^{-1} = (1-(2+3+\cdots+n))^{-1} = -\dfrac{2}{n^2+n-4}.$$
From here, it shouldn't be too hard to compute $\|A^{-1}\|_{\infty}$ exactly or at least get a lower bound. I suspect the last row has the largest absolute row sum.