I have the following proposition:
Theorem: For every invertible matrix $A\in\mathbb{R}^{n\times n}$ and every matrix norm $\|\cdot\|$, then the condition number $\mathcal{K}(A):=\|A\|\cdot\|A^{-1}\|$ satisfies,
$$\frac1{\mathcal{K}(A)}\leq\min\left\{\frac{\|A-B\|}{\|A\|}\ |\ \det(B)=0\right\}$$
Proving this is equivalent to proving that $\|A^{-1}\|\cdot\|A-B\|\geq1$ for every singular matrix $B\in\mathbb{R}^{n\times n}$.
But honestly, I have no idea how to proceed becuase the matrix norm is arbitrary and not necessarily satisfies the sub-multiplicative property. Any hint?
Edit: I know that if $\|\cdot\|_*$ is and induced norm, then it's sub-multiplicative and compatible:
$$\|AB\|_*\leq\|A\|_*\cdot\|B\|_*,\quad\text{for every $A,B\in\mathbb{R}^{n\times n}$}$$
$$\|A\boldsymbol{x}\|_*\leq\|A\|_*\cdot\|\boldsymbol{x}\|_*,\quad\text{for every $A\in\mathbb{R}^{n\times n}$ and every $\boldsymbol{x}\in\mathbb{R}^n$}$$
With these properties the proof is simple.
Proof (for induced norms): Let $A\in\mathbb{R}^{n\times n}$ invertible and $B\in\mathbb{R}^{n\times n}$ singular. Then, there is $\boldsymbol{x}\in\mathbb{R}^n\setminus\{\boldsymbol{0}\}$ such that $B\boldsymbol{x}=\boldsymbol{0}$. Therefore, $B\boldsymbol{x}=(A+B-A)\boldsymbol{x}=A\boldsymbol{x}-(A-B)\boldsymbol{x}=\boldsymbol{0}$. Then, $A\boldsymbol{x}=(A-B)\boldsymbol{x}$ and since $A$ is invertible, $\boldsymbol{x}=A^{-1}(A-B)\boldsymbol{x}$.
Using the previously mentioned properties, then:
$$
\begin{array}{rcl}
\|\boldsymbol{x}\|_*&=&\|A^{-1}(A-B)\boldsymbol{x}\|_*\\
&\leq&\|A^{-1}(A-B)\|_*\cdot\|\boldsymbol{x}\|_*\\
&\leq&\|A^{-1}\|_*\cdot\|A-B\|_*\cdot\|\boldsymbol{x}\|_*
\end{array}
$$
Since $\boldsymbol{x}\neq\boldsymbol{0}$, then $\|\boldsymbol{x}\|_*\neq\boldsymbol{0}$. Simplifying we get $\|A^{-1}\|_*\cdot\|A-B\|_*\geq1$ and since $B$ is an arbitrary singular matrix, the proof is done. $\blacksquare$
So, I think using the fact that all norms in $\mathbb{R}^{n\times n}$ are equivalent we have that there are $r,s\in\mathbb{R}^+$ such that $r\|A\|\leq\|A\|_*\leq s\|A\|$ for every $A\in\mathbb{R}^{n\times n}$. Therefore,
$$1\leq\|A^{-1}\|_*\cdot\|A-B\|_*\leq s^2\|A^{-1}\|\cdot\|A-B\|$$
However, we don't know if $s\leq1$, in fact it's not always the case. This theorem may only apply for sub-multiplicative and compatible norms, I'm trying to figure out a counterexample. I am going on the right way?
Best Answer
The statement is false. Consider the max norm, like here. So the counterexample is:
$A := \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ is invertible and $B := \begin{pmatrix} 1/4 & 1/2 \\ 1/2 & 1 \end{pmatrix}$ is singular.
$$\|A^{-1}\| \cdot \|A-B\| = 1 \cdot \left\|\begin{pmatrix} 3/4 & -1/2 \\ -1/2 & 0 \end{pmatrix} \right\| = \frac{3}{4} < 1$$
The problem is indeed the absence of sub-multiplicative property. But if a matrix norm have this property then, the statement become true by the following lemma.
Lemma: Let $\|\cdot\|$ be a matrix norm on $\mathbb{R}^{n \times n}$. If $\|\cdot\|$ is sub-multiplicative, then there is a vector norm $\|\cdot\|_*$ on $\mathbb{R}^n$ such that both norms are compatible.
Proof: Fix $\boldsymbol{0} \neq \boldsymbol{y} \in \mathbb{R}^n$. Define $\|\cdot\|_* : \mathbb{R}^n \to [0,\infty)$ such that $\|\boldsymbol{x}\|_* := \|\boldsymbol{x}\boldsymbol{y}^T\|$ for every $\boldsymbol{x} \in \mathbb{R}^n$.
It's easy to check that $\|\cdot\|_*$ is a well defined vector norm because $\boldsymbol{y} \neq \boldsymbol{0}$ and the propierties of $\|\cdot\|$ for being, by hyphothesis, a sub-multiplicative matrix norm. So let's just check compatibility.
Let $A \in \mathbb{R}^{n \times n}$ and $\boldsymbol{x} \in \mathbb{R}^n$. Then by sub-multiplicative property of $\|\cdot\|$ we have $$\|A\boldsymbol{x}\|_* = \|(A\boldsymbol{x})\boldsymbol{y}^T\| = \|A(\boldsymbol{x}\boldsymbol{y}^T)\| \leq \|A\| \cdot \|\boldsymbol{x}\boldsymbol{y}^T\| = \|A\| \cdot \|\boldsymbol{x}\|_*$$
Hence $\|\cdot\|$ is compatible with $\|\cdot\|_*$. $\blacksquare$
Then we are done since in the edited part of my post I had already demonstrated the result when we have sub-multiplicative and compatibility properties.