16
$\begingroup$

Let $A$ and $B$ be two real, $n\times n$ matrices. Using Hadamard's inequality, it is not hard to show that $$ \left|\det A - \det B \right| \leq \|A-B\|_{2} \frac{\|A\|_{2}^n -\|B\|_{2}^n}{\|A\|_2 -\|B\|_2}. $$ Where $\|A\|_2=\sqrt{\sum_{i,j}a_{ij}^2}$. From this, I can derive a sup bound, for example $$ \left|\det A - \det B \right| \leq n^{n+1} \|A-B\|_{\infty} \max (\|A\|_{\infty}^{n-1},\|B\|_{\infty}^{n-1}). $$ Where $\|A\|_\infty=\sup_{i,j}|a_{ij}|$.

The constant $n^{n+1}$ is not the best bound possible : any reference (or proof) for a better (or the best) one? I show below that one can obtain $n^2(n-1)^{n-1}$, but that isn't much better. I just tried $10^5$ random matrices on Maple and obtained a maximal constant (much) smaller than one : this is not a proof, but it looks like there is room for improvement nevertheless.


Just for completeness (and in case someone sees a factor I missed), to get the first bound, writing $A=[A_1,\ldots,A_n]$ in terms of its column vectors, an expansion shows \begin{eqnarray*} \det A &=& \det (A_1 -B_1,A_2,\ldots,A_n) + \det (B_1,A_2,\ldots,A_n) \\ &=& \sum_{j=1}^n \det (B_1,\ldots, B_{j-1}, A_j -B_j,A_{j+1},\ldots,A_n) \\ && + \det B, \end{eqnarray*} Thus by Hadamard's inequality, \begin{eqnarray*} \det A -\det B &\leq& \sum_{j=1}^n \prod_{i=1}^{j-1} \|B_i\|_{2}\prod_{i=j+1}^{n} \|A_i\|_{2} \|A_j-B_j\|_{2} \\ &\leq& \|A-B\|_{2} \sum_{j=1}^n \|B\|^{j-1}_{2}\|A\|^{n-j}_{2} \\ &=& \|A-B\|_{2} \frac{\|A\|_{2}^n -\|B\|_{2}^n}{\|A\|_2 -\|B\|_2}. \end{eqnarray*}

The second bound is just that $x^n -y^n\leq n \max(|x|^{n-1},|y|^{n-1}) |x-y|$ and $\|A\|_2 \leq n\|A\|_\infty$.


Another approach is calculus, namely, to write that $\det B - \det A = f(1)-f(0)$, with $f(t)=\det(A + t(B-A))$.

By the mean value theorem $f(1)-f(0)\leq \max |f^\prime (t)|$.

We can compute that $$f^\prime(t) = {\rm trace}\left({\rm Cofm}(A +t(B-A))(B-A)\right)$$ (if I did not mess up, using the formula for the differential of a determinant, where Cofm means the matrix of Cofactors).

Then, it should deliver something better, if there is a nice way to bound it. The simplest thing is to use Cauchy-Schwarz, namely $$ \left|{\rm trace}\left({\rm Cofm}(A +t(B-A))(B-A)\right)\right|\leq \|B-A\|_{2} \|{\rm Cofm}(A +t(B-A))\|_{2} $$ and then, by lack of a better idea, $$ \|{\rm Cofm}(A +t(B-A))\|_{2}\leq n \max_{ij} |{\rm Cof}_{i,j}(A +t(B-A))|, $$ and brutally, $|{\rm Cof}_{i,j}(A +t(B-A))|\leq ((n-1) \max(\|A\|_\infty,\|B\|_\infty))^{n-1}$ gives a slightly better constant, namely $$ n^2(n-1)^{n-1} <n^{n+1} $$ but that still seems a very rough way to bound a determinant, as it is never sharp, since to attain this bound all coefficients should be equal, and therefore the cofactor would be zero. They are of the same order in $n$, and I suspect this order is wrong.

$\endgroup$
8
+100
$\begingroup$

Since the most of related results seem to be published in articles devoted to the perturbation of determinant, let me rewrite your bound $$ \big\vert \, \det \left(\,A\,\right) - \det \left(\,B\,\right)\,\big\rvert \le n^{n+1} \left\|\,A-B\,\right\|_\infty \max \big\{ \left\|\,A\,\right\|^{n-1}_\infty, \,\left\|\,B\,\right\|^{n-1}_\infty \big\}\tag{1a}\label{1a} $$ under assumption $\,B = A + E$: $$ \big\vert \, \det \left(\,A\,\right) - \det \left(\,A+E\,\right)\,\big\rvert \le n^{n+1} \left\|\,E\,\right\|_\infty \max \big\{ \left\|\,A\,\right\|^{n-1}_\infty, \,\left\|\,A+E\,\right\|^{n-1}_\infty \big\}\tag{1b}\label{1b} $$

The best bound I could find is presented in this paper:

Absolute perturbation bounds (Theorem 2.12, p.768, [1]):

Let $A$ and $E$ be $n \times n$ complex matrices. Then $$ \big\vert \, \det \left(\,A\,\right) - \det \left(\,A+E\,\right)\,\big\rvert \le n \,\left\|\,E\,\right\|_2 \max \big\{ \left\|\,A\,\right\|_2, \,\left\|\,A+E\,\right\|_2 \big\}^{n-1} \tag{2}\label{2} $$

Relative perturbation bounds (Corollary 2.14, p.770, [1]):

Let $A$ and $E$ be $n \times n$ complex matrices. If $A$ is nonsingular, then $$ \frac{ \big\vert \, \det \left(\,A+E\,\right) - \det\left(\,A\,\right)\,\big\rvert }{ \big\vert\,\det \left(\,A\,\right)\,\big\rvert } \le \Big( \big\|\,A^{-1}\,\big\|_2 \big\|\,E\,\big\|_2\Big)^{n}-1 = \left(\kappa\,\frac{\left\|\,E\,\right\|_2}{\left\|\,A\,\right\|_2}\right)^{n}-1, \tag{3}\label{3} $$ where $ \kappa \equiv \big\|\,A\,\big\|_2 \,\big\|\,A^{-1}\,\big\|_2$.

The absolute bound result can be rewritten in terms of singular values of $A$.

Absolute perturbation bounds (Corollary 2.7, p.767, [1]): Let $A$ and $E$ be $n \times n$ complex matrices. Then $$\big\vert \, \det \left(\,A\,\right) - \det \left(\,A+E\,\right)\,\big\rvert \le\sum_{i=1}^{n} s_{n-i} \left\|E\right\|^i_2.\tag{2a}\label{2a}$$ If $\operatorname{rank}\left(A\right) = r$ for some $1 ≤ r ≤ n − 1$, then $$\big\vert \det \left(\,A+E\,\right)\big\rvert \le\left\|E\right\|^{n-r}_2 \sum_{i=1}^{r} s_{r-i} \left\|E\right\|^i_2,$$ where the $s_j$ are elementary symmetric functions in the $r$ largest singular values of $A$, $1 ≤ j ≤ r$. The bounds hold with equality for $E = \varepsilon UV_*$ with $ε > 0$, where $ A = UΣV_*$ is a SVD of $A$.


Let us compare, for example, $\eqref{1b}$ and $\eqref{2}$. Since $$ \frac{1}{\sqrt n}\left\|\,E\,\right\|_\infty \le \left\|\,E\,\right\|_2 \le \sqrt n\left\|\,E\,\right\|_\infty \implies \left\|\,E\,\right\|_\infty \ge n^{-\frac{1}{2}} \left\|\,E\,\right\|_2 , $$ we have $$ \begin{aligned} \eqref{1b} & = n^{n+1} \left\|\,E\,\right\|_\infty \max \big\{ \left\|\,A\,\right\|^{n-1}_\infty, \,\left\|\,A+E\,\right\|^{n-1}_\infty \big\} \ge \\ & \ge n^{n} \left( n^{-\frac{1}{2}}\left\|\,E\,\right\|_2\right) \max\big\{\left\|\,A\,\right\|_\infty,\,\left\|\,A+E\,\right\|_\infty\big\}^{n-1} = \\ & = n^{n+\frac{1}{2}} \left\|\,E\,\right\|_2 \max\big\{\left\|\,A\,\right\|_\infty,\,\left\|\,A+E\,\right\|_\infty\big\}^{n-1} \ge \\ & \ge n^{\frac{n}{2}+1} \left\|\,E\,\right\|_2 \max\Big\{\!\!\left( n^{-\frac{1}{2}}\left\|\,A\,\right\|_2\right), \, \left( n^{-\frac{1}{2}}\left\|\,A+E\,\right\|_2\right)\!\!\Big\}^{n-1} = \\ & = n^{\frac{n+3}{2}}\left\|\,E\,\right\|_2 n^{\frac{1-n}{2}} \max\Big\{\left\|\,A\,\right\|_2,\,\left\|\,A+E\,\right\|_2 \Big\}^{n-1} = \\ & = n^{2} \left\|\,E\,\right\|_2 \max\Big\{\left\|\,A\,\right\|_2,\,\left\|\,A+E\,\right\|_2 \Big\}^{n-1} \ge \\ & \ge n \left\|\,E\,\right\|_2 \max \big\{ \left\|\,A\,\right\|_2, \,\left\|\,A+E\,\right\|_2 \big\}^{n-1} = \eqref{2} \end{aligned} $$

Thus, we conclude that the estimate $\eqref{2}$ is sharper than $\eqref{1b}$.


Reference:

  1. Ipsen, Ilse C. F., and Rizwana Rehman. "Perturbation Bounds for Determinants and Characteristic Polynomials." SIAM. J. Matrix Anal. & Appl. SIAM Journal on Matrix Analysis and Applications 30.2 (2008): 762-76. Web. 7 Aug. 2015.
$\endgroup$
  • $\begingroup$ Sorry for not giving the bounty right away (I had gone on vacation), luckily the site did it for me. Thank you. A little disagreement with your bounds at the beginning of the comparison (but it does not matter). Since the size of $E$ is $n^2$, it should be $n$, not $\sqrt{n}$. $\endgroup$ – username Aug 18 '15 at 20:13
  • $\begingroup$ ...which means (2) is better than (1b), but just by $\geq$, without a factor. And it isn't so clearly better than (1b) with $n^2(n-1)^{n-1}$ for large $n$. $\endgroup$ – username Nov 14 '17 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.