Question

Show that fewer thane.n! Algebraic operations (additions and multiplications) are required to compute the determinant of a$\mathbf{n}\mathbf{\times }\mathbf{n}$ matrix by Laplace expansion. Hint: Let ${\mathit{L}}_{\mathbf{n}}$is the number of operations required to compute the determinant of a "general"$\mathit{n}\mathbf{\times }\mathit{n}$ matrix by Laplace expansion. Find a formula expressing${\mathit{L}}_{\mathbf{n}}$ in terms of ${\mathit{L}}_{\mathbf{n}\mathbf{-}\mathbf{1}}$. Use this formula to show, by induction (see Appendix B.1), that$\frac{{\mathbf{L}}_{\mathbf{n}}}{\mathbf{n}\mathbf{!}}\mathbf{=}\mathbf{1}\mathbf{+}\mathbf{1}\mathbf{+}\frac{\mathbf{1}}{\mathbf{2}\mathbf{!}}\mathbf{+}\frac{\mathbf{1}}{\mathbf{3}\mathbf{!}}\mathbf{+}\mathit{L}\mathbf{+}\frac{\mathbf{1}}{\left(n-1\right)\mathbf{!}}\mathbf{-}\frac{\mathbf{1}}{\mathbf{n}\mathbf{!}}$ Use the Taylor series of ${\mathit{e}}^{\mathbf{x}}\mathbf{,}{\mathit{e}}^{\mathbf{x}}\mathbf{=}\mathbf{\sum }_{\mathbf{n}\mathbf{-}\mathbf{0}}^{\mathbf{\infty }}\frac{{\mathbf{x}}^{\mathbf{n}}}{\mathbf{n}\mathbf{!}}$, to show that the right-hand side of this equation is less than e.

Short answer

Therefore, the expression of $L_n$is given by, $L_n<en!,Ɐn\in \mathrm{\mathbb{N}}$.

Step-by-step solution

Definition 

A determinant is a unique number associated with asquare matrix.

A determinant is a scalar value that is a function of the entries of a square matrix.

It is the signed factor by which areas are scaled by this matrix. If the sign is negative the matrix reverses orientation.

To find the formula expressing in  Ln terms

Let$L_n$ be the number of algebraic operations required to calculate the determinant of a$n\times n$ matrix using the Laplace expansion. We have:

$L_1=0,L_n=n\left(L_{n-1}+2\right)-1$,This gives us:

$\frac{L_n}{n!}=\frac{L_{n-1}}{\left(n-1\right)!}+\frac{2}{\left(n-1\right)!}-\frac{1}{n!}$This, in recursion, gives us:

role="math" localid="1660718145433" $\frac{L_n}{n!}=1+1+\frac{1}{2!}+\frac{1}{3!}+...+\frac{1}{\left(n-1\right)!}-\frac{1}{n!}<\sum _{n-0}^{\infty }\frac{1}{n!}$

$\frac{L_n}{n!}=E$ Which, finally, gives us $L_n<en!,Ɐn\in \mathrm{\mathbb{N}}$.