1
$\begingroup$

I have three questions:

1) For the determinant of a matrix $Q \in \mathbb{R}^{n \times n}$, there is the following polynomial formula: $$ \det(Q)= \sum_\sigma \text{sgn}(\sigma) \prod_{i=1}^{n} Q_{\sigma(i),i} \tag{*} $$ I know about the characteristic polynomial of a matrix whose roots are the eigenvalues, but I am not sure about how (*) comes about? In particular, what is $\sigma$ here and is $Q_{\sigma(i),i}$ the element at the $\sigma(i)$-th row and $i$-th column of $Q$? Would $\text{sgn}(\sigma) $ ever be negative?

2) As a follow up, let $\|Q\|_\infty$ be the largest absolute value of the elements of the $Q$ matrix, and let $\|Q\|$ be the operator norm, then, applying (*) to the below, we have $$ \begin{split} & |\det(I+Q)-1| \\&= \left| \prod_{i=1}^{n} (1+Q_{i,i})-1 + \sum_{\sigma\neq\text{id}} \text{sgn}(\sigma) \prod_{i=1}^{n} (\delta_{\sigma(i),i}+Q_{\sigma(i),i}) \right| \\ \end{split} \tag{**} $$

Can someone please explain how each of the two terms come about in (**)? I believe that the first term captures the diagonal components of $Q$ and the second term are the off-diagonals? Not sure what the $\delta_{\sigma(i), i}$ means though.

3) Finally, I would like to find a better upper bound for $(**)$ than the one given by @JoonasIlmavirta as

\begin{split} & |\det(I+Q)-1| \\&= \left| \prod_{i=1}^{n} (1+Q_{i,i})-1 + \sum_{\sigma\neq\text{id}} \text{sgn}(\sigma) \prod_{i=1}^{n} (\delta_{\sigma(i),i}+Q_{\sigma(i),i}) \right| \\&\leq \left| \prod_{i=1}^{n} (1+Q_{i,i})-1 \right| + \sum_{\sigma\neq\text{id}} \left| \prod_{i=1}^{n} (\delta_{\sigma(i),i}+Q_{\sigma(i),i}) \right| \\&\leq (2^n-1)\times\|Q\|_\infty + (n!-1)\times 2^{n-1}\|Q\|_\infty \\&\leq 2^nn!\|Q\|_\infty. \end{split}

Each term in the product $\left| \prod_{i=1}^{n} (\delta_{\sigma(i),i}+Q_{\sigma(i),i}) \right|$ above is at most $2$ in absolute value, and there is at least one $i$ so that $\delta_{\sigma(i),i}=0$, so the product is at most $2^{n-1}\|Q\|_\infty$ in absolute value. The rest of the estimates are similar.

$\endgroup$
  • $\begingroup$ It's just defined that way. That's the definition. Some guy thought it up. $\endgroup$ – The Great Duck Aug 4 '17 at 23:20
  • $\begingroup$ @Typhon thanks for your reply. But, I am confused about the terms there. Do you have a reference for where I can read about it? I couldn't find this form by doing a quick google search. though I did come across characteristic polynomials of a matrix. Is this the same thing? $\endgroup$ – user2457324 Aug 4 '17 at 23:22
  • 1
    $\begingroup$ @Typhon The Leibniz formula can be used as a definition - especially for people to be able to calculate them without needing to understand what they are - but "some guy thought it up" is a misleading perspective. Determinants measure signed volume in the case of reals, which for geometric reasons entails it is invariant under certain elementary row operations and subsequently is a multilinear, alternating function of its columns. By working it out by hand and noticing the pattern, we can induct to obtain Leibniz formula. $\endgroup$ – anon Aug 5 '17 at 0:51
  • 1
    $\begingroup$ @Sentient and OP: $\sigma$ refers to any of the $5!=120$ possible permutations of the set $\{1,\cdots,5\}$. $\endgroup$ – anon Aug 5 '17 at 0:53
  • 1
    $\begingroup$ Yes, $w^{-1}d=w^{-1}\color{Red}{+}w^{-1}(d-1)$. $\endgroup$ – anon Aug 5 '17 at 1:18
2
+50
$\begingroup$

Here is the story of my quest for the bounds. I put $\varepsilon=\|Q\|_\infty$ and split the quest into two parts.

The first of them was for upper bounds for $\det(I+Q)-1$. Clearly, they follow from upper bounds for $|\det(I+Q)|$. We have $\|I+Q\|_\infty\le 1+\varepsilon$, so $|\det(I+Q)|\le (1+2\varepsilon+n\varepsilon^2)^{n/2}$, by Hadamard’s inequality. Compare it with the bound $2^nn!\varepsilon$ which you have (as I guess, for $\varepsilon\le 1$). By Stirling’s formula, there exists a number $0<\theta<1$ such that $n!=\sqrt{2\pi n}\left(\frac ne\right)^n e^{\frac \theta{12n}}$. Thus $2^nn!\varepsilon\simeq n^n(2/e)^n\varepsilon$, so Hadamard’s inequality based bound is better. On the other hand, it is almost tight for big $\varepsilon$ (and at least some $n$), because $|\det (1+\varepsilon H_n)|\simeq |\varepsilon H_n|=\varepsilon^nn^{n/2}$, where $H_n$ is a Hadamard matrix of order $n$ (provided it exists for such $n$). In case when you are interested only in small $\varepsilon\le 1$, I conjectured that this lower bound can be improved. From the other hand, I looked for inequalities applicable to bounds for $|\det(I+Q)-1|$ in “Inequalities” by Edwin F. Beckenbach and Richard Bellman and “Introduction to matrix analysis” by the latter, and found none, besides already used Hadamard’s inequality.

So I started the quest for lower bounds for $\det(I+Q)-1$. Of course, it is at least $-|\det(I+Q)|-1$, so we can apply here the upper bounds for $|\det(I+Q)|$ from the first part of the quest. For big $\varepsilon$ the summand $-1$ is not essential, so we stop here.

Cleary, if $\det(I+Q)=0$ then we are done. So we may assume the converse. Then provided $\det(I+Q)>0$ (so we put $\varepsilon<1$) we can bound it using the equlity $\det(I+Q)=1/\det (I+Q)^{-1}$, represent the matrix $(I+Q)^{-1}$ as $I+P$ with $\|P\|_\infty$ small and then apply use for $\det(I+P)$ the upper bounds from the first part of the quest.

For instance, for $\varepsilon<1/n$ the series $-Q+Q^2-Q^3\dots$ converges, and I guess we can put as $P$ its limit. In this case $$\|P\|_\infty\le \varepsilon+n\varepsilon^2+n^2\varepsilon^3+\dots=\frac\varepsilon{1-n\varepsilon} .$$

An other, straightforward way to bound $\det (I+Q)^{-1}$ using the adjugate matrix of $I+Q$, but this way is complicate, uses the inductive bounds for minors, and I guess that finally it’ll give a weak bound.

But I came to idea to use bounds following from Gauss elimination method for solving systems of linear equations, which looked much more promising.

But at this point I decided to google and found relevant results, which already were partially overlapping with mine. Namely, I found a paper “Note on best possible bounds for determinants of matrices close to the identity matrix” [BOS2] by Richard P. Brent, Judy-anne H. Osborn, and Warren D. Smith.

My prize was that bound $\det(I+Q)\ge 1−n\varepsilon$ for $\varepsilon<1/n$ is known from Ostrowski’s paper from 1938. Bounds based on Gauss elimination method are worse. This is not so surprising, because Ostrowski’s bound is best-possible, as it is attained if $Q =-\varepsilon J$, where $J$ is the $n\times n$ matrix of all ones.

On the other hand, as it sometimes happens in a life of a professional mathematician, the upper bound $|\det(I+Q)|\le (1+2\varepsilon+n\varepsilon^2)^{n/2}$ was already proven (two years ago by the same way) in Theorem 2 of [BOS2]. The authors also remarked that this bound is best-possible if a skew-Hadamard matrix $H$ of order $n$ exists. To see this, consider $I+Q=(1 + \varepsilon)I + \varepsilon(H − I)$. Such a matrix exists for $n =1, 2$, all multiples of four up to and including $4\times × 68$, as well as infinitely many larger $n$, such as all powers of two, see [CD]. Sharp bounds for small orders for which a skew-Hadamard matrix does not exist (e.g. $n=3$) are considered in [BOS1, §4.1].

References

[BOS1] Richard P. Brent, Judy-anne H. Osborn, Warren D. Smith, Bounds on determinants of perturbed diagonal matrices, arXiv:1401.7048v7, 2014.

[BOS2] Richard P. Brent, Judy-anne H. Osborn, Warren D. Smith, Note on best possible bounds for determinants of matrices close to the identity matrix, Linear Algebra and its Applications, 466 (2015), 21–26.

[CD] C.J. Colbourn, J.H. Dinitz, Handbook of Combinatorial Designs, 2nd edition, CRC Press, New York, 2006.

[O] A.M. Ostrowski, Sur l’approximation du déterminant de Fredholm par les déterminants des systèmes d’equations linéaires, Ark. Math. Stockholm Ser. A, 26 (1938), 1–15.

$\endgroup$
  • $\begingroup$ Hi -- many thanks for the references! I read BOS2 a bit and was just wondering whether or not the upper bound held only for small $\epsilon = \| Q \|_\infty $ or doesn't matter? Also, if have that $Q = AB$, then, can the above be simplified -- I know that $\| AB \|_\infty \leq \| A \| \| B \|$ ... I am just wondering how the upper bound can be simplified since there is that power $\frac{n}{2}$. Thank you again and please take a look at this math.stackexchange.com/questions/2387250/… if you may have a chance. Any suggestions would be appreciated! $\endgroup$ – user2457324 Aug 9 '17 at 22:30
  • $\begingroup$ @user2457324 The upper bound is derived from Hadamard’s inequality. It holds for each $\varepsilon>0$. $\endgroup$ – Alex Ravsky Aug 10 '17 at 3:59
  • $\begingroup$ I didn't got the next question (about $Q=AB$). Also, why this case is easier? For instance, when $B=I$, we have $Q=A$ and have the same problem for $A$, isn’t it? $\endgroup$ – Alex Ravsky Aug 10 '17 at 4:03
  • $\begingroup$ Thanks for the first one. Not saying it is easier, but just was wondering how to expand the upper bound for when $Q = AB$: $| \det (I + AB) | \leq (1 + 2 \| AB \|_\infty + n \| AB \|_\infty^2 )^{\frac{n}{2}} $ but not sure how to upper bound the expression above using the induced norm and sub-multiplicative property. Would appreciate any assistance on doing that. $\endgroup$ – user2457324 Aug 10 '17 at 4:30
  • $\begingroup$ @user2457324 I think that without additional restrictions on $A$ and $B$, giving restrictions on $Q$, decomposition $Q=AB$ doesn’t help to strengthen the upper bound. $\endgroup$ – Alex Ravsky Aug 10 '17 at 4:36
4
$\begingroup$

(1) $\sigma$ ranges over elements of $S_n$, i.e. permutations of $\{1,\cdots,n\}$, and $\mathrm{sgn}(\sigma)$ refers to the sign of the permutation ($+1$ if it is an even permutation, $-1$ if it is an odd permutation). Geometrically, permutations of coordinates are preserve or reverse the orientation of space exactly when the sign of the permutation is positive of negative.

Let's work this out by hand with $n=3$. In one-line notation for permutations, here are all of the $3!=6$ permutations of $\{1,2,3\}$ and their signs:

$$ \begin{array}{ccc} \color{Red}{(123),+} & \color{Lime}{(132),-} & \color{Blue}{(213),-} \\ (231),+ & (312),+ & (321),- \end{array} $$

Therefore, we have (using the above permutations in this order)

$$ \large \det\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} = \begin{array}{l} \color{Red}{+}a_{\color{Red}{1}1}a_{\color{Red}{2}2}a_{\color{Red}{3}3} \color{Lime}{-}a_{\color{Lime}{1}1}a_{\color{Lime}{3}2}a_{\color{Lime}{2}3}\color{Blue}{-}a_{\color{Blue}{2}1}a_{\color{Blue}{1}2}a_{\color{Blue}{3}3} \\ +a_{21}a_{32}a_{13}+a_{31}a_{12}a_{23}-a_{31}a_{22}a_{13}. \end{array} $$

(Sorry for lime green's harshness, normal green is too close to black.)

(2) The entries of the identity matrix $I$ are the Kronecker delta function $\delta_{ij}$ (which is $1$ when $i=j$ and $0$ otherwise). The sum over all permutations can be split into two: the term when $\sigma=\mathrm{id}$ is the identity map, and all of the other terms when $\sigma\ne \mathrm{id}$. In the first case, $\mathrm{id}(i)=i$ for all $i$ and $\mathrm{sgn}(\mathrm{id})=+1$ so the summand is $+\prod_{i=1}^n (1+Q_{ii})$.

$\endgroup$
  • $\begingroup$ thanks so very much for this! I would really appreciate it if you can look at the inequality part at your earliest convenience. But, for now, do you think that finding the lower bound is the right intuition to go about satisfying that determinant inequality? Also, I would really like to avoid $\det(W) \leq 1$. Pls do take a look at this...it would be much appreciated! $\endgroup$ – user2457324 Aug 5 '17 at 1:47
  • $\begingroup$ Also, a quick question so I feel comfortable--if $W$ is a symmetric positive definite matrix, and $Z$ is just a symmetric matrix, then, this doesn't imply that $\det(I + WZ) \geq 1$ correct? $\endgroup$ – user2457324 Aug 5 '17 at 1:51
  • 2
    $\begingroup$ Nope it doesn't, e.g. $W=[\begin{smallmatrix}1&0\\0&1\end{smallmatrix}]$ and $Z=[\begin{smallmatrix}0&1\\1&0\end{smallmatrix}]$. $\endgroup$ – anon Aug 5 '17 at 2:23

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.