On the polynomial formula for determinants 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.
 A: (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})$.
A: 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.
