\makeatletter \providecommand*{\input@path}{} \g@addto@macro{\input@path}{{./legrand-orange-book_v3/}{../../legrand-orange-book_v3/}} \makeatother \PassOptionsToPackage{unicode}{hyperref} \PassOptionsToPackage{hyphens}{url} \PassOptionsToPackage{dvipsnames,svgnames,x11names}{xcolor} \documentclass[11pt,a4paper]{LegrandOrangeBook} % Compatibility with Pandoc 3 captionless longtables. Older longtable % versions still try to step the synthetic `none` caption counter. \makeatletter \@ifundefined{c@none}{\newcounter{none}}{} \makeatother \usepackage[most]{tcolorbox} \setcounter{secnumdepth}{3} \usepackage{iftex} \usepackage{float} % Abilita l'opzione H \usepackage{caption} % Per una migliore gestione delle didascalie \usepackage{cancel} \usepackage{mathtools} \usepackage{graphicx} % Per le figure \graphicspath{{./}{./legrand-orange-book_v3/Images/}{../../legrand-orange-book_v3/Images/}} \ifPDFTeX \usepackage{grffile} % Per gestire percorsi file complessi % pdfLaTeX configuration \usepackage{mathrsfs} %\usepackage{FiraSans} \usepackage{bm} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{newunicodechar} \else % XeLaTeX/LuaLaTeX configuration \usepackage{fontspec} \usepackage{unicode-math} \usepackage{newunicodechar} % Inter per il testo %\setmainfont{Noto Sans} % Libertinus per la matematica %\setmathfont{STIX Two Math} %\setmainfont{Fira Sans} %\setmonofont{Fira Code} \let\bm\symbf \fi % Lettere greche minuscole \newunicodechar{α}{\ensuremath{\alpha}} \newunicodechar{β}{\ensuremath{\beta}} \newunicodechar{γ}{\ensuremath{\gamma}} \newunicodechar{δ}{\ensuremath{\delta}} \newunicodechar{ε}{\ensuremath{\epsilon}} \newunicodechar{ζ}{\ensuremath{\zeta}} \newunicodechar{η}{\ensuremath{\eta}} \newunicodechar{θ}{\ensuremath{\theta}} \newunicodechar{ι}{\ensuremath{\iota}} \newunicodechar{κ}{\ensuremath{\kappa}} \newunicodechar{λ}{\ensuremath{\lambda}} \newunicodechar{μ}{\ensuremath{\mu}} \newunicodechar{ν}{\ensuremath{\nu}} \newunicodechar{ξ}{\ensuremath{\xi}} \newunicodechar{π}{\ensuremath{\pi}} \newunicodechar{ρ}{\ensuremath{\rho}} \newunicodechar{σ}{\ensuremath{\sigma}} \newunicodechar{τ}{\ensuremath{\tau}} \newunicodechar{υ}{\ensuremath{\upsilon}} \newunicodechar{φ}{\ensuremath{\phi}} \newunicodechar{χ}{\ensuremath{\chi}} \newunicodechar{ψ}{\ensuremath{\psi}} \newunicodechar{ω}{\ensuremath{\omega}} % Lettere greche maiuscole \newunicodechar{Α}{\ensuremath{A}} \newunicodechar{Β}{\ensuremath{B}} \newunicodechar{Γ}{\ensuremath{\Gamma}} \newunicodechar{Δ}{\ensuremath{\Delta}} \newunicodechar{Ε}{\ensuremath{E}} \newunicodechar{Ζ}{\ensuremath{Z}} \newunicodechar{Η}{\ensuremath{H}} \newunicodechar{Θ}{\ensuremath{\Theta}} \newunicodechar{Ι}{\ensuremath{I}} \newunicodechar{Κ}{\ensuremath{K}} \newunicodechar{Λ}{\ensuremath{\Lambda}} \newunicodechar{Μ}{\ensuremath{M}} \newunicodechar{Ν}{\ensuremath{N}} \newunicodechar{Ξ}{\ensuremath{\Xi}} \newunicodechar{Ο}{\ensuremath{O}} \newunicodechar{Π}{\ensuremath{\Pi}} \newunicodechar{Ρ}{\ensuremath{P}} \newunicodechar{Σ}{\ensuremath{\Sigma}} \newunicodechar{Τ}{\ensuremath{T}} \newunicodechar{Υ}{\ensuremath{\Upsilon}} \newunicodechar{Φ}{\ensuremath{\Phi}} \newunicodechar{Χ}{\ensuremath{X}} \newunicodechar{Ψ}{\ensuremath{\Psi}} \newunicodechar{Ω}{\ensuremath{\Omega}} % Pedici \newunicodechar{₀}{\textsubscript{0}} \newunicodechar{₁}{\textsubscript{1}} \newunicodechar{₂}{\textsubscript{2}} \newunicodechar{₃}{\textsubscript{3}} \newunicodechar{₄}{\textsubscript{4}} \newunicodechar{₅}{\textsubscript{5}} \newunicodechar{₆}{\textsubscript{6}} \newunicodechar{₇}{\textsubscript{7}} \newunicodechar{₈}{\textsubscript{8}} \newunicodechar{₉}{\textsubscript{9}} % Apici \newunicodechar{⁰}{\textsuperscript{0}} \newunicodechar{¹}{\textsuperscript{1}} \newunicodechar{²}{\textsuperscript{2}} \newunicodechar{³}{\textsuperscript{3}} \newunicodechar{⁴}{\textsuperscript{4}} \newunicodechar{⁵}{\textsuperscript{5}} \newunicodechar{⁶}{\textsuperscript{6}} \newunicodechar{⁷}{\textsuperscript{7}} \newunicodechar{⁸}{\textsuperscript{8}} \newunicodechar{⁹}{\textsuperscript{9}} % Simboli matematici \newunicodechar{−}{\ensuremath{-}} % Unicode minus \newunicodechar{±}{\ensuremath{\pm}} % ± \newunicodechar{≤}{\ensuremath{\leq}} % ≤ \newunicodechar{≥}{\ensuremath{\geq}} % ≥ \newunicodechar{×}{\ensuremath{\times}}% × \newunicodechar{∂}{\ensuremath{\partial}} % ∂ \newunicodechar{∞}{\ensuremath{\infty}} % ∞ \usepackage{color} \usepackage{fancyvrb} \newcommand{\VerbBar}{|} \newcommand{\VERB}{\Verb[commandchars=\\\{\}]} \DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}} % Add ',fontsize=\small' for more characters per line \newenvironment{Shaded}{}{} \newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}} \newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}} \newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}} \newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}} \newcommand{\BuiltInTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{#1}} \newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}} \newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}} \newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}} \newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}} \newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}} \newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}} \newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}} \newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}} \newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}} \newcommand{\ExtensionTok}[1]{#1} \newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}} \newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}} \newcommand{\ImportTok}[1]{\textcolor[rgb]{0.00,0.50,0.00}{\textbf{#1}}} \newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}} \newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}} \newcommand{\NormalTok}[1]{#1} \newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}} \newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}} \newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}} \newcommand{\RegionMarkerTok}[1]{#1} \newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}} \newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}} \newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}} \newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}} \newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}} \newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}} \usepackage{longtable,booktabs,array} \usepackage{calc} % for calculating minipage widths % Correct order of tables after \paragraph or \subparagraph \usepackage{etoolbox} \makeatletter \patchcmd\longtable{\par}{\if@noskipsec\mbox{}\fi\par}{}{} \makeatother % Allow footnotes in longtable head/foot \IfFileExists{footnotehyper.sty}{\usepackage{footnotehyper}}{\usepackage{footnote}} \makesavenoteenv{longtable} \usepackage{graphicx} \makeatletter \newsavebox\pandoc@box \newcommand*\pandocbounded[1]{% scales image to fit in text height/width \sbox\pandoc@box{#1}% \Gscale@div\@tempa{\textheight}{\dimexpr\ht\pandoc@box+\dp\pandoc@box\relax}% \Gscale@div\@tempb{\linewidth}{\wd\pandoc@box}% \ifdim\@tempb\p@<\@tempa\p@\let\@tempa\@tempb\fi% select the smaller of both \ifdim\@tempa\p@<\p@\scalebox{\@tempa}{\usebox\pandoc@box}% \else\usebox{\pandoc@box}% \fi% } % Set default figure placement to htbp \def\fps@figure{htbp} \makeatother % definitions for citeproc citations \NewDocumentCommand\citeproctext{}{} \NewDocumentCommand\citeproc{mm}{% \begingroup\def\citeproctext{#2}\cite{#1}\endgroup} \makeatletter % allow citations to break across lines \let\@cite@ofmt\@firstofone % avoid brackets around text for \cite: \def\@biblabel#1{} \def\@cite#1#2{{#1\if@tempswa , #2\fi}} \makeatother \newlength{\cslhangindent} \setlength{\cslhangindent}{1.5em} \newlength{\csllabelwidth} \setlength{\csllabelwidth}{3em} \newenvironment{CSLReferences}[2] % #1 hanging-indent, #2 entry-spacing {\begin{list}{}{% \setlength{\itemindent}{0pt} \setlength{\leftmargin}{0pt} \setlength{\parsep}{0pt} % turn on hanging indent if param 1 is 1 \ifodd #1 \setlength{\leftmargin}{\cslhangindent} \setlength{\itemindent}{-1\cslhangindent} \fi % set entry spacing \setlength{\itemsep}{#2\baselineskip}}} {\end{list}} \usepackage{calc} \newcommand{\CSLBlock}[1]{\hfill\break\parbox[t]{\linewidth}{\strut\ignorespaces#1\strut}} \newcommand{\CSLLeftMargin}[1]{\parbox[t]{\csllabelwidth}{\strut#1\strut}} \newcommand{\CSLRightInline}[1]{\parbox[t]{\linewidth - \csllabelwidth}{\strut#1\strut}} \newcommand{\CSLIndent}[1]{\hspace{\cslhangindent}#1} \setlength{\emergencystretch}{3em} % prevent overfull lines \providecommand{\tightlist}{% \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}} \definecolor{quarto-callout-color}{HTML}{909090} \definecolor{quarto-callout-note-color}{HTML}{0758E5} \definecolor{quarto-callout-important-color}{HTML}{CC1914} \definecolor{quarto-callout-warning-color}{HTML}{EB9113} \definecolor{quarto-callout-tip-color}{HTML}{00A047} \definecolor{quarto-callout-caution-color}{HTML}{FC5300} \definecolor{quarto-callout-color-frame}{HTML}{acacac} \definecolor{quarto-callout-note-color-frame}{HTML}{4582ec} \definecolor{quarto-callout-important-color-frame}{HTML}{d9534f} \definecolor{quarto-callout-warning-color-frame}{HTML}{f0ad4e} \definecolor{quarto-callout-tip-color-frame}{HTML}{02b875} \definecolor{quarto-callout-caution-color-frame}{HTML}{fd7e14} \hypersetup{ pdftitle={Linear and Numerical Linear Algebra Dictionary}, pdfauthor={Enrico Bertolazzi}, colorlinks=true, linkcolor={blue}, filecolor={Maroon}, citecolor={Blue}, urlcolor={Blue}, pdfcreator={LaTeX via pandoc}} \usepackage{fontawesome5} % Per LaTeX moderno \definecolor{ocre}{RGB}{243, 102, 25} % Define the color used for highlighting throughout the book \chapterimage{orange1.jpg} % Chapter heading image \chapterspaceabove{6.5cm} % Default whitespace from the top of the page to the chapter title on chapter pages \chapterspacebelow{6.75cm} % Default amount of vertical whitespace from the top margin to the start of the text on chapter pages \usepackage{bookmark} % Importantissimo: dopo hyperref! \newtheorem{lemmaT}{Lemma}[chapter] % Theorems, the first argument is the theorem name, the second the theorem \newenvironment{lemma}{\begin{tBox}\begin{lemmaT}}{\end{lemmaT}\end{tBox}} \newtheorem{remarkT}{Remark}[chapter] % Theorems, the first argument is the theorem name, the second the theorem \newenvironment{refremark}{\begin{tBox}\begin{remarkT}}{\end{remarkT}\end{tBox}} \begin{document} %---------------------------------------------------------------------------------------- % TITLE PAGE %---------------------------------------------------------------------------------------- \titlepage % Output the title page {\includegraphics[width=\paperwidth]{background.pdf}} % Code to output the background image, which should be the same dimensions as the paper to fill the page entirely; leave empty for no background image { % Title(s) and author(s) \centering\sffamily % Font styling {\Huge\bfseries Linear and Numerical Linear Algebra Dictionary\par} % Book title \vspace{16pt} % Vertical whitespace {\LARGE Matrices, Factorizations, and Numerical Methods\par} % Subtitle \vspace{24pt} % Vertical whitespace {\huge\bfseries Enrico Bertolazzi\par} % Author name } %---------------------------------------------------------------------------------------- % COPYRIGHT PAGE %---------------------------------------------------------------------------------------- \thispagestyle{empty} % Suppress headers and footers on this page ~\vfill % Push the text down to the bottom of the page \noindent Copyright \copyright\ 2026 Enrico Bertolazzi\\ % Copyright notice \noindent \textsc{University of Trento}\\ % Publisher \noindent \textsc{\href{https://www.latextemplates.com/template/legrand-orange-book}{book-website.com}}\\ % URL \noindent Licensed under the Creative Commons Attribution-NonCommercial 4.0 License (the ``License''). You may not use this file except in compliance with the License. You may obtain a copy of the License at \url{https://creativecommons.org/licenses/by-nc-sa/4.0}. Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \textsc{``as is'' basis, without warranties or conditions of any kind}, either express or implied. See the License for the specific language governing permissions and limitations under the License.\\ % License information, replace this with your own license (if any) \noindent \textit{English edition, 2026} % Printing/edition date %---------------------------------------------------------------------------------------- % TABLE OF CONTENTS %---------------------------------------------------------------------------------------- \pagestyle{empty} % Disable headers and footers for the following pages \tableofcontents % Output the table of contents %\listoffigures % Output the list of figures, comment or remove this command if not required %\listoftables % Output the list of tables, comment or remove this command if not required \pagestyle{fancy} % Enable default headers and footers again \cleardoublepage % Start the following content on a new page \bookmarksetup{startatroot} \chapter{Basic Notation}\label{basic-notation} \index{basic notation@Basic Notation} \begin{tcolorbox}[enhanced jigsaw, arc=.35mm, bottomrule=.15mm, bottomtitle=1mm, breakable, colback=white, colbacktitle=quarto-callout-note-color!10!white, colframe=quarto-callout-note-color-frame, coltitle=black, left=2mm, leftrule=.75mm, opacityback=0, opacitybacktitle=0.6, rightrule=.15mm, title={Purpose and Scope}, titlerule=0mm, toprule=.15mm, toptitle=1mm] This is not a set of lecture notes. It is a compact dictionary of definitions and results used in the accompanying courses. If you want to study any of these topics, you should follow a course or consult a textbook devoted to the subject. This dictionary is intended for readers who already know, or have previously studied, the material and need a concise reference whenever a reminder is useful. \end{tcolorbox} The following \(A\in\mathbb{K}^{m\times n}\), with \(\mathbb{K}=\mathbb{R}\) or \(\mathbb{C}\). For square plates \(A\in\mathbb{K}^{n\times n}\): \[A^T=\text{transpose},\qquad A^*=\overline{A}^{\,T}=\text{conjugate transpose}.\] In the real field \(A^*=A^T\). \[\mathop{\mathrm{spec}}(A)=\{\lambda\in\mathbb{C}:\det(A-\lambda I)=0\}, \qquad \rho(A)=\max_{\lambda\in\mathop{\mathrm{spec}}(A)}|\lambda|.\] \bookmarksetup{startatroot} \chapter{Summary Table}\label{summary-table} \index{summary table@Summary Table} {\def\LTcaptype{none} % do not increment counter \begin{longtable}[]{@{} >{\raggedright\arraybackslash}p{(\linewidth - 6\tabcolsep) * \real{0.2500}} >{\raggedright\arraybackslash}p{(\linewidth - 6\tabcolsep) * \real{0.2500}} >{\raggedright\arraybackslash}p{(\linewidth - 6\tabcolsep) * \real{0.2500}} >{\raggedright\arraybackslash}p{(\linewidth - 6\tabcolsep) * \real{0.2500}}@{}} \toprule\noalign{} \begin{minipage}[b]{\linewidth}\raggedright \textbf{Type} \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright \textbf{Defining condition} \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright \textbf{Eigenvalues} \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright \textbf{Key properties} \end{minipage} \\ \midrule\noalign{} \endhead \bottomrule\noalign{} \endlastfoot Diagonal & \(a_{ij}=0\) for \(i\neq j\) & diagonal elements & diagonal inverse if not singular \\ Scale & \(A=\alpha I\) & all equal to \(\alpha\) & switch with every matrix \\ Triangular & \(a_{ij}=0\) above or below the diagonal & diagonal elements & \(\det A=\prod_i a_{ii}\) \\ Real symmetric & \(A^T=A\) & real & diagonally orthogonally \\ Real antisymmetrical & \(A^T=-A\) & pure imaginary or \(0\) & diagonal nothing \\ Hermitian & \(A^*=A\) & real & unitarily diagonalizable \\ Antihermitiana & \(A^*=-A\) & pure imaginary or \(0\) & \(iA\) Hermitian \\ Orthogonal & \(A^TA=I\) & \(\vert \lambda\vert =1\) & \(A^{-1}=A^T\), \(\det A=\pm1\) \\ Unitarian & \(A^*A=I\) & \(\vert \lambda\vert =1\) & \(A^{-1}=A^*\) \\ Normal & \(A^*A=AA^*\) & complexes in general & unitarily diagonalizable \\ SPD & \(A=A^T\), \(x^TAx>0\) & positive & Cholesky, invertible \\ SPSD & \(A=A^T\), \(x^TAx\ge0\) & nonnegative & Gram, square root \\ negative definite & \(A=A^T\), \(x^TAx<0\) & negative & \(-A\) SPD \\ Indefinite & square shape of variable sign & positive and negative & not semidefinite \\ Idempotent & \(A^2=A\) & \(0,1\) & projector, \(\mathop{\mathrm{rank}}A=\mathop{\mathrm{tr}}A\) \\ Involution & \(A^2=I\) & \(\pm1\) & \(A^{-1}=A\) \\ Nilpotent & \(A^k=0\) & only \(0\) & \(\det A=0\) \\ Permutation & one unit per line/column & roots of unity & orthogonal \\ Householder & \(H=I-2vv^T/(v^Tv)\) & \(\pm1\) & symmetric and orthogonal \\ Toeplitz & \(a_{ij}=t_{i-j}\) & --- & constant diagonals \\ Hankel & \(a_{ij}=h_{i+j}\) & --- & constant antidiagonal \\ Circulating & rows obtained for cyclic shift & DFT of coefficients & diagonalized by DFT \\ Vandermonde & \(V_{ij}=x_i^{j-1}\) & --- & known instrument \\ Companion & associated with a polynomial & roots of polynomial & norm matrix for polynomials \\ Stocha & elements \(\ge0\), row/column sums \(=1\) & contains \(\lambda=1\) & \(\rho(A)=1\) \\ Gram Matrix & \(G=B^*B\) & nonnegative & positive semidefinite Hermitian \\ \end{longtable} } \bookmarksetup{startatroot} \chapter{Inner Products}\label{inner-products} \index{inner products@Inner Products} \section{Real Inner Product}\label{real-inner-product} \index{real inner product@Real Inner Product} A product to scale up \(\mathbb{R}^n\) is a function \[\langle x,y\rangle\] that satisfies: \begin{itemize} \item bilinearity; \item symmetry; \item positivity: \end{itemize} \[\langle x,x\rangle\ge0;\] \begin{itemize} \tightlist \item defined: \end{itemize} \[\langle x,x\rangle=0 \iff x=0.\] Product euclide inner: \[\langle x,y\rangle=x^Ty.\] \section{Complex Inner Product}\label{complex-inner-product} \index{complex inner product@Complex Inner Product} Up \(\mathbb{C}^n\): \[\langle x,y\rangle=x^*y.\] Property: \[\langle x,y\rangle = \overline{\langle y,x\rangle}.\] \section{Weighted Inner Product}\label{weighted-inner-product} \index{weighted inner product@Weighted Inner Product} \[M=M^*\succ0,\] then \[\langle x,y\rangle_M=x^*My.\] The associated norm is: \[\|x\|_M=\sqrt{x^*Mx}.\] \bookmarksetup{startatroot} \chapter{Vector Norms}\label{vector-norms} \index{vector norms@Vector Norms} A vector rule meets: \[\|x\|\ge0,\] \[\|x\|=0\iff x=0,\] \[\|\alpha x\|=|\alpha|\,\|x\|,\] \[\|x+y\|\le\|x\|+\|y\|.\] \section{\texorpdfstring{\(1\)-Norm}{1-Norm}}\label{norm} \index{1-norm@1-Norm} \[\|x\|_1=\sum_{i=1}^n|x_i|.\] \section{\texorpdfstring{\(2\)-Norm}{2-Norm}}\label{norm-1} \index{2-norm@2-Norm} \[\|x\|_2= \sqrt{\sum_{i=1}^n|x_i|^2} = \sqrt{x^*x}.\] \section{Infinity Norm}\label{infinity-norm} \index{infinity norm@Infinity Norm} \[\|x\|_\infty=\max_i|x_i|.\] \section{\texorpdfstring{\(p\)-Norm}{p-Norm}}\label{p-norm} \index{p-norm@p-Norm} For \[1\le p<\infty:\] \[\|x\|_p= \left( \sum_i|x_i|^p \right)^{1/p}.\] \section{Cauchy--Schwarz Inequality}\label{cauchyschwarz-inequality} \index{cauchy-schwarz inequality@Cauchy–Schwarz Inequality} For norms induced by scalar product: \[|\langle x,y\rangle| \le \|x\|\,\|y\|.\] \section{Equivalence of Norms in Finite Dimensions}\label{equivalence-of-norms-in-finite-dimensions} \index{equivalence of norms in finite dimensions@Equivalence of Norms in Finite Dimensions} Up \(\mathbb{K}^n\) all norms are equivalent. In particular: \[\|x\|_\infty \le \|x\|_2 \le \sqrt n\,\|x\|_\infty,\] \[\|x\|_2 \le \|x\|_1 \le \sqrt n\,\|x\|_2.\] \bookmarksetup{startatroot} \chapter{Matrix Norms}\label{matrix-norms} \index{matrix norms@Matrix Norms} A matrix norm meets the properties of a norm on the matrix space. A matrix rule is submultiplicative if: \[\|AB\| \le \|A\|\,\|B\|.\] \section{Induced Matrix Norm}\label{induced-matrix-norm} \index{induced matrix norm@Induced Matrix Norm} Date a vector rule: \[\|A\| = \max_{x\neq0} \frac{\|Ax\|}{\|x\|} = \max_{\|x\|=1}\|Ax\|.\] Induced norms are automatically compatible with the vector norm: \[\|Ax\| \le \|A\|\,\|x\|.\] \section{\texorpdfstring{Matrix \(1\)-Norm}{Matrix 1-Norm}}\label{matrix-1-norm} \index{matrix 1-norm@Matrix 1-Norm} \[\|A\|_1 = \max_j \sum_i|a_{ij}|.\] It is the maximum of the sum of the absolute values along the columns. \section{Matrix Infinity Norm}\label{matrix-infinity-norm} \index{matrix infinity norm@Matrix Infinity Norm} \[\|A\|_\infty = \max_i \sum_j|a_{ij}|.\] It is the maximum of the sum of the absolute values along the rows. \section{\texorpdfstring{Matrix \(2\)-Norm}{Matrix 2-Norm}}\label{matrix-2-norm} \index{matrix 2-norm@Matrix 2-Norm} \[\|A\|_2 = \sigma_{\max}(A) = \sqrt{\lambda_{\max}(A^*A)}.\] \(A\) is normal: \[\|A\|_2 = \rho(A).\] \(A\) is symmetric/Hermitian: \[\|A\|_2 = \max_i|\lambda_i|.\] \section{Frobenius Norm}\label{frobenius-norm} \index{frobenius norm@Frobenius Norm} \[\|A\|_F = \sqrt{ \sum_{i,j}|a_{ij}|^2 }.\] Equivalently: \[\|A\|_F = \sqrt{\mathop{\mathrm{tr}}(A^*A)} = \sqrt{ \sum_i\sigma_i^2 }.\] Property: \[\|A\|_2 \le \|A\|_F \le \sqrt{\mathop{\mathrm{rank}}(A)}\,\|A\|_2.\] Frobenius is not a norm induced by a vector norm, but is submultiplicative: \[\|AB\|_F \le \|A\|_F\|B\|_F.\] In addition: \[\|AB\|_F \le \|A\|_2\|B\|_F,\] \[\|AB\|_F \le \|A\|_F\|B\|_2.\] \bookmarksetup{startatroot} \chapter{Compatibility between Norms}\label{compatibility-between-norms} \index{compatibility between norms@Compatibility between Norms} A matrix norm \(\|\cdot\|_M\) is compatible with a vector rule \(\|\cdot\|_v\) if: \[\|Ax\|_v \le \|A\|_M\|x\|_v.\] Any induced matrix rule is compatible with the vector norm from which it is induced. For norm norms: \[\|Ax\|_1 \le \|A\|_1\|x\|_1,\] \[\|Ax\|_2 \le \|A\|_2\|x\|_2,\] \[\|Ax\|_\infty \le \|A\|_\infty\|x\|_\infty.\] \bookmarksetup{startatroot} \chapter{Norms and Inner Products}\label{norms-and-inner-products} \index{norms and inner products@Norms and Inner Products} Each inner product induces a norm: \[\|x\| = \sqrt{\langle x,x\rangle}.\] Not every norm is induced by a scalar product. A norm is induced by a scalar product if and only if it meets the identity of the parallelogram: \[\|x+y\|^2+\|x-y\|^2 = 2\|x\|^2+2\|y\|^2.\] For the Euclidean rule: \[\|x\|_2=\sqrt{x^*x}.\] For a positive SPD/Hermitian matrix \(M\): \[\|x\|_M=\sqrt{x^*Mx}.\] \bookmarksetup{startatroot} \chapter{Dual, Frobenius, and Unitarily Invariant Norms}\label{dual-frobenius-and-unitarily-invariant-norms} \index{dual frobenius and unitarily invariant norms@Dual, Frobenius, and Unitarily Invariant Norms} The dual rule is ' \[\|y\|_*=\max_{\|x\|\le1}|y^*x|.\] \(1/p+1/q=1\): \[(\|\cdot\|_p)^*=\|\cdot\|_q, \qquad |x^*y|\le\|x\|_p\|y\|_q.\] Frobenius inner product \[\langle A,B\rangle_F=\mathop{\mathrm{tr}}(A^*B), \qquad \|A\|_F=\sqrt{\mathop{\mathrm{tr}}(A^*A)}.\] For \(U,V\) Units: \[\|UAV\|_2=\|A\|_2,\qquad \|UAV\|_F=\|A\|_F.\] Schatten rules: \[\|A\|_{S_p}=\left(\sum_i\sigma_i^p\right)^{1/p}.\] Nuclear norms: \[\|A\|_*=\sum_i\sigma_i.\] \bookmarksetup{startatroot} \chapter{Fundamental Subspaces and Rank}\label{fundamental-subspaces-and-rank} \index{fundamental subspaces and rank@Fundamental Subspaces and Rank} Both \(A\in\mathbb{K}^{m\times n}\) and \(\mathop{\mathrm{rank}}(A)=r\). The four basic subspaces are \[\mathop{\mathrm{range}}(A)\subseteq\mathbb{K}^m,\qquad \ker(A)\subseteq\mathbb{K}^n,\] \[\mathop{\mathrm{range}}(A^*)\subseteq\mathbb{K}^n,\qquad \ker(A^*)\subseteq\mathbb{K}^m.\] The size is \[\dim\mathop{\mathrm{range}}(A)=\dim\mathop{\mathrm{range}}(A^*)=r, \quad \dim\ker(A)=n-r, \quad \dim\ker(A^*)=m-r.\] Theorem rank--nulled': \[\mathop{\mathrm{rank}}(A)+\dim\ker(A)=n.\] Basic orthogonal relations: \[\mathop{\mathrm{range}}(A)^\perp=\ker(A^*),\qquad \mathop{\mathrm{range}}(A^*)^\perp=\ker(A),\] \[\mathbb{K}^m=\mathop{\mathrm{range}}(A)\oplus\ker(A^*),\qquad \mathbb{K}^n=\mathop{\mathrm{range}}(A^*)\oplus\ker(A).\] \bookmarksetup{startatroot} \chapter{Rank and Invertibility: Equivalent Conditions}\label{rank-and-invertibility-equivalent-conditions} \index{rank and invertibility equivalent conditions@Rank and Invertibility: Equivalent Conditions} For \(A\in\mathbb{K}^{n\times n}\) are equivalent: \begin{align*} &A\text{ invertible},\\ &\mathop{\mathrm{rank}}(A)=n,\\ &\det(A)\neq0,\\ &0\notin\mathop{\mathrm{spec}}(A),\\ &\ker(A)=\{0\},\\ &Ax=0\Rightarrow x=0,\\ &\text{the columns of }A\text{ are linearly independent},\\ &\text{the rows of }A\text{ are linearly independent}. \end{align*} \bookmarksetup{startatroot} \chapter{Rectangular Matrices}\label{rectangular-matrices} \index{rectangular matrices@Rectangular Matrices} \section{Full-Rank Matrix}\label{full-rank-matrix} \index{full-rank matrix@Full-Rank Matrix} For \(A\in\mathbb{K}^{m\times n}\): \[\mathop{\mathrm{rank}}(A)=\min(m,n).\] \(m\ge n\) and \(\mathop{\mathrm{rank}}(A)=n\), \(A\) has full rank for columns. \(m\le n\) and \(\mathop{\mathrm{rank}}(A)=m\), \(A\) has full rank for rows. \section{Matrix with Orthonormal Columns}\label{matrix-with-orthonormal-columns} \index{matrix with orthonormal columns@Matrix with Orthonormal Columns} \[Q^*Q=I.\] \(Q\) is rectangular, in general: \[QQ^*\neq I.\] \(QQ^*\) is the orthogonal projector on \(\mathop{\mathrm{range}}(Q)\). \section{Matrix with Orthonormal Rows}\label{matrix-with-orthonormal-rows} \index{matrix with orthonormal rows@Matrix with Orthonormal Rows} \[QQ^*=I.\] In this case \(Q^*Q\) He\textquotesingle s an orthogonal projector. \bookmarksetup{startatroot} \chapter{Basic Properties of the Determinant, Trace, and Spectrum}\label{basic-properties-of-the-determinant-trace-and-spectrum} \index{basic properties of the determinant trace and spectrum@Basic Properties of the Determinant, Trace, and Spectrum} For \(A,B\in\mathbb{K}^{n\times n}\): \[\det(AB)=\det(A)\det(B),\] \[\det(A^T)=\det(A), \qquad \det(A^*)=\overline{\det(A)},\] \[\det(A^{-1})=\frac{1}{\det A},\] \[\mathop{\mathrm{tr}}(AB)=\mathop{\mathrm{tr}}(BA),\] \[\mathop{\mathrm{tr}}(A)=\sum_{i=1}^n\lambda_i,\] \[\det(A)=\prod_{i=1}^n\lambda_i,\] where the eigenvalues are counted with a multiplicity of algebraic. \(B=S^{-1}AS\), then \(A\) and \(B\) are similar and have: \begin{itemize} \item same characteristic polynomial; \item same eigenvalues; \item itself decisive; \item same trace; \item same rank. \end{itemize} \bookmarksetup{startatroot} \chapter{Eigenvalues, Spectrum, and Spectral Radius}\label{eigenvalues-spectrum-and-spectral-radius} \index{eigenvalues spectrum and spectral radius@Eigenvalues, Spectrum, and Spectral Radius} \[Av=\lambda v,\qquad v e0, \qquad p_A(\lambda)=\det(\lambda I-A).\] For each eigenvalue: \[1\le m_g(\lambda)\le m_a(\lambda).\] Useful transformations: \[\mathop{\mathrm{spec}}(A^{-1})=\{\lambda^{-1}:\lambda\in\mathop{\mathrm{spec}}(A)\}, \quad \mathop{\mathrm{spec}}(A+\alpha I)=\mathop{\mathrm{spec}}(A)+\alpha,\] \[\mathop{\mathrm{spec}}(\alpha A)=\alpha\mathop{\mathrm{spec}}(A),\qquad \mathop{\mathrm{spec}}(A^k)=\{\lambda^k:\lambda\in\mathop{\mathrm{spec}}(A)\}.\] For each polynomial \(p\): \[\mathop{\mathrm{spec}}(p(A))=p(\mathop{\mathrm{spec}}(A)).\] The spectral radius is \[\rho(A)=\max_{\lambda\in\mathop{\mathrm{spec}}(A)}|\lambda|.\] For each induced matrix rule: \[\rho(A)\le\|A\|.\] Gelfand formula: \[\rho(A)=\lim_{k\to\infty}\|A^k\|^{1/k}.\] In finite dimensions: \[A^k\to0\iff\rho(A)<1.\] \section{Gershgorin's Theorem}\label{gershgorins-theorem} \index{gershgorin� s theorem@Gershgorin’s Theorem} \[\mathop{\mathrm{spec}}(A)\subseteq\bigcup_i \left\{z\in\mathbb{C}:|z-a_{ii}|\le\sum_{j e i}|a_{ij}|\right\}.\] \bookmarksetup{startatroot} \chapter{Spectral Theorem and Rayleigh Quotient}\label{spectral-theorem-and-rayleigh-quotient} \index{spectral theorem and rayleigh quotient@Spectral Theorem and Rayleigh Quotient} For \(A=A^*\): \[A=U\Lambda U^*,\qquad \Lambda\in\mathbb{R}^{n\times n}.\] In the symmetric real case: \[A=Q\Lambda Q^T.\] Rayleigh quotient is \[R_A(x)=\frac{x^*Ax}{x^*x}.\] For \(A=A^*\): \[\lambda_{\min}\le R_A(x)\le\lambda_{\max},\] \[\lambda_{\min}=\min_{x e0}R_A(x),\qquad \lambda_{\max}=\max_{x e0}R_A(x).\] Ordering \(\lambda_1\le\cdots\le\lambda_n\) Courant--Fischer provides \[\lambda_k=\min_{\dim S=k}\max_{0 e x\in S}R_A(x) =\max_{\dim S=n-k+1}\min_{0 e x\in S}R_A(x).\] \bookmarksetup{startatroot} \chapter{Diagonalizability and Canonical Forms}\label{diagonalizability-and-canonical-forms} \index{diagonalizability and canonical forms@Diagonalizability and Canonical Forms} \section{Diagonalizable Matrix}\label{diagonalizable-matrix} \index{diagonalizable matrix@Diagonalizable Matrix} \(A\) is diagonalized if there is an invertible matrix \(V\) such that \[A=V\Lambda V^{-1},\] with \(\Lambda\) diagonal. Equival to the existence of a base constituted by motorists. Sufficient conditions: \begin{itemize} \item \(A\) he has \(n\) distinct eigenvalues; \item \(A\) is normal on \(\mathbb{C}\); \item \(A\) is real symmetric. \end{itemize} \section{Defective Matrix}\label{defective-matrix} \index{defective matrix@Defective Matrix} A non- diagonalized matrix is called defective. For at least one eigenvalue: \[\dim\ker(A-\lambda I) < \text{algebraic multiplicity of }\lambda.\] \section{Jordan Form}\label{jordan-form} \index{jordan form@Jordan Form} Each complex matrix is similar to a block matrix: \[A=VJV^{-1},\] where \(J\) consists of Jordan blocks \[J_k(\lambda)= \begin{pmatrix} \lambda&1&&\\ &\lambda&\ddots&\\ &&\ddots&1\\ &&&\lambda \end{pmatrix}.\] \bookmarksetup{startatroot} \chapter{Schur Decomposition}\label{schur-decomposition} \index{schur decomposition@Schur Decomposition} For each \(A\in\mathbb{C}^{n\times n}\): \[A=QTQ^*,\] with \(Q\) unitary and \(T\) superior triangular. The diagonal elements of \(T\) are the eigenvalues of \(A\). In the real case there is a form of real Schur with diagonal blocks \(1\times1\) and \(2\times2\). \(A\) is normal, \(T\) is diagonal. Schur\textquotesingle s form is numerically stable; Jordan\textquotesingle s form is mainly theoretical. \bookmarksetup{startatroot} \chapter{Elementary and Structured Matrices}\label{elementary-and-structured-matrices} \index{elementary and structured matrices@Elementary and Structured Matrices} \section{Zero Matrix}\label{zero-matrix} \index{zero matrix@Zero Matrix} \[A=0.\] Property: \begin{itemize} \item \(\mathop{\mathrm{rank}}(A)=0\). \item \(\mathop{\mathrm{spec}}(A)=\{0\}\). \item \(A\) is nilpotent, symmetric/Hermitian, normal and semidefinite positive and negative. \end{itemize} \section{Identity Matrix}\label{identity-matrix} \index{identity matrix@Identity Matrix} \[I_n=\mathop{\mathrm{diag}}(1,\dots,1).\] Property: \begin{itemize} \item \(I_nA=AI_n=A\). \item \(I_n^{-1}=I_n\). \item \(\mathop{\mathrm{spec}}(I_n)=\{1\}\). \item It is diagonal, symmetric, Hermitian, orthogonal, unitary, normal, SPD. \end{itemize} \section{Diagonal Matrix}\label{diagonal-matrix} \index{diagonal matrix@Diagonal Matrix} \[D=\mathop{\mathrm{diag}}(d_1,\dots,d_n).\] Property: \begin{itemize} \item \(\mathop{\mathrm{spec}}(D)=\{d_1,\dots,d_n\}\). \item \(\det D=\prod_i d_i\). \item \(\mathop{\mathrm{rank}}D=\) number of diagonal elements not null. \item \(D\) is invertible if and only if \(d_i\neq0\) for each \(i\). \item In this case \[D^{-1}=\mathop{\mathrm{diag}}(d_1^{-1},\dots,d_n^{-1}).\] \end{itemize} \section{Scalar Matrix}\label{scalar-matrix} \index{scalar matrix@Scalar Matrix} \[A=\alpha I.\] Property: \begin{itemize} \item switched with each square matrix of the same size; \item \(\mathop{\mathrm{spec}}(A)=\{\alpha\}\); \item \(\det A=\alpha^n\); \item is invertible if and only if \(\alpha\neq0\). \end{itemize} \section{Upper and Lower Triangular Matrices}\label{upper-and-lower-triangular-matrices} \index{upper and lower triangular matrices@Upper and Lower Triangular Matrices} Upper triangular: \[a_{ij}=0\qquad i>j.\] Lower triangular: \[a_{ij}=0\qquad i1.\] Property: \begin{itemize} \item tridiagonal linear systems can be solved in \(O(n)\) operations; \item if symmetric, it is completely described by the main diagonal and an adjacent diagonal. \end{itemize} \section{Band Matrix}\label{band-matrix} \index{band matrix@Band Matrix} Ha. \[a_{ij}=0 \qquad\text{for}\qquad i-j>p \quad\text{or}\quad j-i>q.\] \(p\)and\(q\) are the lower and upper band semi-ampies. \section{Hessenberg Matrix}\label{hessenberg-matrix} \index{hessenberg matrix@Hessenberg Matrix} Upper Hessenberg: \[a_{ij}=0\qquad i>j+1.\] Lower Hessenberg: \[a_{ij}=0\qquad j>i+1.\] Each square matrix can be reduced by unit/orthogonal similarities in the shape of Hessenberg. \section{Block Matrix}\label{block-matrix} \index{block matrix@Block Matrix} \[A= \begin{pmatrix} A_{11} & A_{12}\\ A_{21} & A_{22} \end{pmatrix}.\] The usual matrix operations apply to blocks when the dimensions are compatible. \(A_{11}\) is invertible, Schur\textquotesingle s complement is \[S=A_{22}-A_{21}A_{11}^{-1}A_{12}.\] \bookmarksetup{startatroot} \chapter{Symmetry, Adjoints, and Normality}\label{symmetry-adjoints-and-normality} \index{symmetry adjoints and normality@Symmetry, Adjoints, and Normality} \section{Real Symmetric Matrix}\label{real-symmetric-matrix} \index{real symmetric matrix@Real Symmetric Matrix} \[A^T=A.\] Property: \begin{itemize} \item all eigenvalues are real; \item autovectors related to separate autovalves are orthogonal; \item exists an orthogonal matrix \(Q\) such that \[A=Q\Lambda Q^T;\] \item is always diagonalized; \item \(\|A\|_2=\rho(A)=\max_i|\lambda_i|\). \end{itemize} \section{Real Skew-Symmetric Matrix}\label{real-skew-symmetric-matrix} \index{real skew-symmetric matrix@Real Skew-Symmetric Matrix} \[A^T=-A.\] Property: \begin{itemize} \item \(a_{ii}=0\); \item eigenvalues are null or pure imaginary; \item if \(n\) is odd, \(\det A=0\); \item \(x^TAx=0\) for each \(x\in\mathbb{R}^n\). \end{itemize} \section{Hermitian Matrix}\label{hermitian-matrix} \index{hermitian matrix@Hermitian Matrix} \[A^*=A.\] Property: \begin{itemize} \item real eigenvalues; \item autovectors associated with distinct eigenvalues are orthogonal; \item exist \(U\) such that \[A=U\Lambda U^*, \qquad \Lambda\in\mathbb{R}^{n\times n}.\] \end{itemize} \section{Skew-Hermitian Matrix}\label{skew-hermitian-matrix} \index{skew-hermitian matrix@Skew-Hermitian Matrix} \[A^*=-A.\] Property: \begin{itemize} \item eigenvalues are pure or null imaginary; \item \(iA\) is Hermitian; \item \(e^A\) is unitary. \end{itemize} \section{Normal Matrix}\label{normal-matrix} \index{normal matrix@Normal Matrix} \[A^*A=AA^*.\] Fundamental equivalences: \begin{itemize} \item \(A\) is normal if and only if it is diagonally diagonally; \item exist \(U\) such that \[A=U\Lambda U^*.\] \end{itemize} They\textquotesingle re normal. \begin{itemize} \item hermitiane matrices; \item antihermitiane; \item unit; \item real symmetries; \item real orthogonals. \end{itemize} \bookmarksetup{startatroot} \chapter{Orthogonal and Unitary Matrices}\label{orthogonal-and-unitary-matrices} \index{orthogonal and unitary matrices@Orthogonal and Unitary Matrices} \section{Orthogonal Matrix}\label{orthogonal-matrix} \index{orthogonal matrix@Orthogonal Matrix} \[Q^TQ=QQ^T=I.\] Property: \begin{itemize} \item \(Q^{-1}=Q^T\); \item preserves scalable product, angles and Euclidean norm: \[\|Qx\|_2=\|x\|_2;\] \item \(|\lambda_i|=1\); \item \(\det Q=\pm1\); \item \(\mathop{\mathrm{cond}}_2(Q)=1\). \end{itemize} \section{Unitary Matrix}\label{unitary-matrix} \index{unitary matrix@Unitary Matrix} \[U^*U=UU^*=I.\] Property: \begin{itemize} \item \(U^{-1}=U^*\); \item preserves hermitian product; \item \(\|Ux\|_2=\|x\|_2\); \item \(|\lambda_i|=1\); \item \(|\det U|=1\). \end{itemize} \section{Rotation Matrix}\label{rotation-matrix} \index{rotation matrix@Rotation Matrix} In \(\mathbb{R}^2\): \[R(\theta)= \begin{pmatrix} \cos\theta & -\sin\theta\\ \sin\theta & \cos\theta \end{pmatrix}.\] Property: \[R^TR=I,\qquad \det R=1.\] \section{Householder Reflection}\label{householder-reflection} \index{householder reflection@Householder Reflection} For \(v\neq0\): \[H=I-2\frac{vv^T}{v^Tv}.\] Property: \begin{itemize} \item \(H^T=H\); \item \(H^TH=I\); \item \(H^{-1}=H\); \item \(H^2=I\); \item \(\det H=-1\); \item eigenvalues: \(-1\) in the direction of \(v\), \(+1\) in the orthogonal subspace. \end{itemize} \section{Givens Rotation}\label{givens-rotation} \index{givens rotation@Givens Rotation} It acts not banally on two coordinates: \[G= \begin{pmatrix} 1&&&&\\ &c&&-s&\\ &&1&&\\ &s&&c&\\ &&&&1 \end{pmatrix}, \qquad c^2+s^2=1.\] It is orthogonal and is used to selectively cancel elements of a matrix. \bookmarksetup{startatroot} \chapter{Definiteness}\label{definiteness} \index{definiteness@Definiteness} \section{Positive Definite Matrix}\label{positive-definite-matrix} \index{positive definite matrix@Positive Definite Matrix} For a symmetric real matrix: \[A\succ0 \quad\Longleftrightarrow\quad x^TAx>0 \quad\forall x\neq0.\] Equivalent properties: \begin{itemize} \item all eigenvalues are positive; \item exists the factorization of Cholesky \[A=LL^T\] with \(L\) lower triangular and positive diagonal; \item all major minors''leading''are positive (Sylvester crime); \item \(A=B^TB\) with \(B\) invertable; \item \(A^{-1}\succ0\). \end{itemize} In addition: \[\det A>0.\] \section{Positive Semidefinite Matrix}\label{positive-semidefinite-matrix} \index{positive semidefinite matrix@Positive Semidefinite Matrix} \[A\succeq0 \quad\Longleftrightarrow\quad x^TAx\ge0 \quad\forall x.\] Property: \begin{itemize} \item non-negative eigenvalues; \item exist \(B\) such that \[A=B^TB;\] \item admits a positive symmetric square root: \end{itemize} \[A^{1/2}A^{1/2}=A.\] \section{Negative Definite Matrix}\label{negative-definite-matrix} \index{negative definite matrix@Negative Definite Matrix} \[A\prec0 \quad\Longleftrightarrow\quad x^TAx<0 \quad\forall x\neq0.\] Equival to \[-A\succ0.\] eigenvalues are all negative. \section{Negative Semidefinite Matrix}\label{negative-semidefinite-matrix} \index{negative semidefinite matrix@Negative Semidefinite Matrix} \[A\preceq0 \quad\Longleftrightarrow\quad x^TAx\le0.\] eigenvalues are not positive. \section{Indefinite Matrix}\label{indefinite-matrix} \index{indefinite matrix@Indefinite Matrix} There are \(x,y\neq0\) such as \[x^TAx>0, \qquad y^TAy<0.\] For a symmetric matrix this is equivalent to the presence of at least one positive eigenvalue and at least one negative. \bookmarksetup{startatroot} \chapter{Matrices Defined by Algebraic Equations}\label{matrices-defined-by-algebraic-equations} \index{matrices defined by algebraic equations@Matrices Defined by Algebraic Equations} \section{Idempotent Matrix}\label{idempotent-matrix} \index{idempotent matrix@Idempotent Matrix} \[P^2=P.\] Property: \begin{itemize} \item eigenvalues in \(\{0,1\}\); \item is diagonalized; \item \[\mathop{\mathrm{rank}}P=\mathop{\mathrm{tr}}P;\] \item represents a projection. \end{itemize} \section{Orthogonal Projector}\label{orthogonal-projector} \index{orthogonal projector@Orthogonal Projector} \[P^2=P, \qquad P^T=P.\] Property: \begin{itemize} \item \(P\) project orthogonally on \(\mathop{\mathrm{range}}(P)\); \item \[\mathbb{R}^n=\mathop{\mathrm{range}}(P)\oplus\ker(P);\] \item \(\|P\|_2=1\) if \(P\neq0\). \end{itemize} \(A\) has linearly independent columns: \[P=A(A^TA)^{-1}A^T\] is the orthogonal projector on \(\mathop{\mathrm{range}}(A)\). \section{Oblique Projector}\label{oblique-projector} \index{oblique projector@Oblique Projector} \[P^2=P, \qquad P^T\neq P.\] The projection takes place along a subspace not necessarily orthogonal to the image subspace. \section{Involutory Matrix}\label{involutory-matrix} \index{involutory matrix@Involutory Matrix} \[A^2=I.\] Property: \begin{itemize} \item \(A^{-1}=A\); \item eigenvalues in \(\{-1,1\}\); \item is diagonalized on different characteristic fields from \(2\). \end{itemize} \section{Nilpotent Matrix}\label{nilpotent-matrix} \index{nilpotent matrix@Nilpotent Matrix} Existing \(k\ge1\) such that \[A^k=0.\] Property: \begin{itemize} \item only eigenvalue: \(0\); \item \(\det A=0\); \item \(\mathop{\mathrm{tr}}A=0\); \item \(I-A\) is always invertible; \item if \(A^k=0\): \end{itemize} \[(I-A)^{-1}=I+A+\cdots+A^{k-1}.\] \section{Unipotent Matrix}\label{unipotent-matrix} \index{unipotent matrix@Unipotent Matrix} \[A=I+N,\] with \(N\) nilpotent. All eigenvalues of \(A\) are equal to \(1\). \bookmarksetup{startatroot} \chapter{Permutation and Sparse Matrices}\label{permutation-and-sparse-matrices} \index{permutation and sparse matrices@Permutation and Sparse Matrices} \section{Permutation Matrix}\label{permutation-matrix} \index{permutation matrix@Permutation Matrix} It is obtained by switching rows or columns \(I\). Property: \begin{itemize} \item contains exactly one \(1\) in each row and column; \item \[P^{-1}=P^T;\] \item is orthogonal; \item \(\det P=\pm1\); \item multiply to the left permutate rows, to the right permutate columns. \end{itemize} \section{Sparse Matrix}\label{sparse-matrix} \index{sparse matrix@Sparse Matrix} A matrix is called scattered when the number of nonzero elements is much lower than \(mn\). The notion is computational, not algebraic. \section{Diagonally Dominant Matrix}\label{diagonally-dominant-matrix} \index{diagonally dominant matrix@Diagonally Dominant Matrix} Dominance by rows: \[|a_{ii}| \ge \sum_{j\neq i}|a_{ij}|.\] Directly dominant: \[|a_{ii}| > \sum_{j\neq i}|a_{ij}|.\] A strictly diagonally dominant matrix is not singular. \bookmarksetup{startatroot} \chapter{Classical Special Matrices}\label{classical-special-matrices} \index{classical special matrices@Classical Special Matrices} \section{Gram Matrix}\label{gram-matrix} \index{gram matrix@Gram Matrix} For carriers \(v_1,\dots,v_n\): \[G_{ij}=\langle v_i,v_j\rangle.\] Equivalently: \[G=V^*V.\] Property: \begin{itemize} \item \(G\) is Hermitian; \item \(G\succeq0\); \item \(G\succ0\) if and only if the carriers are linearly independent; \item \[\mathop{\mathrm{rank}}(G)=\mathop{\mathrm{rank}}(V).\] \end{itemize} \section{Vandermonde Matrix}\label{vandermonde-matrix} \index{vandermonde matrix@Vandermonde Matrix} \[V= \begin{pmatrix} 1&x_1&x_1^2&\cdots&x_1^{n-1}\\ 1&x_2&x_2^2&\cdots&x_2^{n-1}\\ \vdots&\vdots&\vdots&&\vdots\\ 1&x_n&x_n^2&\cdots&x_n^{n-1} \end{pmatrix}.\] determinant: \[\det V= \prod_{1\le i0\] means \[a_{ij}>0 \quad\forall i,j.\] Not to be confused with''definita positiva''. \section{Row-Stochastic Matrix}\label{row-stochastic-matrix} \index{row-stochastic matrix@Row-Stochastic Matrix} \[a_{ij}\ge0, \qquad \sum_j a_{ij}=1.\] Property: \begin{itemize} \item \[A\mathbf{1}=\mathbf{1};\] \item \(1\) is eigenvalue; \item \(\rho(A)=1\). \end{itemize} \section{Column-Stochastic Matrix}\label{column-stochastic-matrix} \index{column-stochastic matrix@Column-Stochastic Matrix} \[a_{ij}\ge0, \qquad \sum_i a_{ij}=1.\] Then \[\mathbf{1}^TA=\mathbf{1}^T.\] \section{Doubly Stochastic Matrix}\label{doubly-stochastic-matrix} \index{doubly stochastic matrix@Doubly Stochastic Matrix} It is stochastic for both rows and columns. Every permutation matrix is bistocastic. \bookmarksetup{startatroot} \chapter{Matrix Classes Used in Numerical Analysis}\label{matrix-classes-used-in-numerical-analysis} \index{matrix classes used in numerical analysis@Matrix Classes Used in Numerical Analysis} \section{\texorpdfstring{\(Z\)-Matrix}{Z-Matrix}}\label{z-matrix} \index{z-matrix@Z-Matrix} A real matrix \(A\) is a \(Z\)- Matrix if \[a_{ij}\le0 \qquad i\neq j.\] \section{\texorpdfstring{\(M\)-Matrix}{M-Matrix}}\label{m-matrix} \index{m-matrix@M-Matrix} One \(M\)-matrix can be represented as \[A=sI-B, \qquad B\ge0, \qquad s\ge\rho(B).\] \[s>\rho(B),\] is a \(M\)- Not unusual matrix. For one \(M\)- not singular matrix: \begin{itemize} \item \(A^{-1}\ge0\); \item eigenvalues have a positive real part; \item \(A\) is a \(Z\)- Matrix. \end{itemize} \section{\texorpdfstring{\(P\)-Matrix}{P-Matrix}}\label{p-matrix} \index{p-matrix@P-Matrix} A square real matrix is a \(P\)-Matrix if all its major minors are positive. Property: \begin{itemize} \item every SPD matrix is a \(P\)-matrix; \item I\textquotesingle ll give you the \(P\)- matrices have a central role in the problems of linear complementarity. \end{itemize} \section{Monotone Matrix}\label{monotone-matrix} \index{monotone matrix@Monotone Matrix} A not singular real matrix \(A\) is called monotonous if \[A^{-1}\ge0.\] \section{Irreducible Matrix}\label{irreducible-matrix} \index{irreducible matrix@Irreducible Matrix} A square matrix is reducible if there is a permutation matrix \(P\) such that \[P^TAP= \begin{pmatrix} A_{11}&A_{12}\\ 0&A_{22} \end{pmatrix}.\] Otherwise it is irreducible. \bookmarksetup{startatroot} \chapter{Important Relationships between Matrix Classes}\label{important-relationships-between-matrix-classes} \index{important relationships between matrix classes@Important Relationships between Matrix Classes} \[\boxed{ A\text{ SPD} \Longrightarrow A\text{ symmetric} \Longrightarrow A\text{ normal} \Longrightarrow A\text{ diagonalizable} }\] \[\boxed{ A\text{ Hermitian} \Longrightarrow A\text{ normal} \Longrightarrow A\text{ unitarily diagonalizable} }\] \[\boxed{ A\text{ unitary} \Longrightarrow A\text{ normal} }\] \[\boxed{ A\text{ orthogonal} \Longrightarrow A\text{ normal} }\] \[\boxed{ A^2=A \Longrightarrow \mathop{\mathrm{spec}}(A)\subseteq\{0,1\} }\] \[\boxed{ A^2=I \Longrightarrow \mathop{\mathrm{spec}}(A)\subseteq\{-1,1\} }\] \[\boxed{ A^k=0 \Longrightarrow \mathop{\mathrm{spec}}(A)=\{0\} }\] \[\boxed{ A=B^*B \Longrightarrow A\succeq0 }\] \[\boxed{ A=B^*B,\ \mathop{\mathrm{rank}}(B)=n \Longrightarrow A\succ0 }\] \bookmarksetup{startatroot} \chapter{Appendix: Terminology Not to Confuse}\label{appendix-terminology-not-to-confuse} \index{appendix terminology not to confuse@Appendix: Terminology Not to Confuse} \begin{itemize} \tightlist \item \textbf{matrix positiva}: \end{itemize} \[a_{ij}>0.\] It is an element property by element. \begin{itemize} \tightlist \item \textbf{matrix definita positiva}: \end{itemize} \[x^TAx>0 \quad\forall x\neq0.\] It is a property of the square form. \begin{itemize} \tightlist \item \textbf{matrix ortogonale}: \end{itemize} \[Q^TQ=I.\] Doesn\textquotesingle t mean the matrix elements are''ortogonali'': rows and columns are orthonormal. \begin{itemize} \item \textbf{matrix diagonalizzabile}does not necessarily mean symmetric. \item \textbf{matrix simmetrica}real is always diagonalized orthogonally. \item \textbf{matrix normale}it is always diagonally, but it is not necessarily Hermitian. \item \textbf{Semidefinita positiva}does not imply invertability. \item \textbf{Strettamente diagonalmente dominante}implies invertability, but not necessarily positive definiteness. \end{itemize} \bookmarksetup{startatroot} \chapter{Block Matrices and the Schur Complement}\label{block-matrices-and-the-schur-complement} \index{block matrices and the schur complement@Block Matrices and the Schur Complement} Both \[M=\begin{pmatrix}A&B\\C&D\end{pmatrix}.\] For a diagonal block matrix: \[\det\begin{pmatrix}A&0\\0&D\end{pmatrix}=\det A\det D, \qquad \begin{pmatrix}A&0\\0&D\end{pmatrix}^{-1} =\begin{pmatrix}A^{-1}&0\\0&D^{-1}\end{pmatrix}.\] \(A\) is invertible, Schur complement \(A\) and \[S_D=D-CA^{-1}B.\] Yes. \[M= \begin{pmatrix}I&0\\CA^{-1}&I\end{pmatrix} \begin{pmatrix}A&B\\0&S_D\end{pmatrix}, \qquad \det M=\det A\det S_D.\] \(A\)and\(S_D\) are invertible: \[M^{-1}=\begin{pmatrix} A^{-1}+A^{-1}BS_D^{-1}CA^{-1}&-A^{-1}BS_D^{-1}\\ -S_D^{-1}CA^{-1}&S_D^{-1} \end{pmatrix}.\] For \(M=M^*\): \[M=\begin{pmatrix}A&B\\B^*&D\end{pmatrix},\quad A\succ0,\] \[M\succ0\iff D-B^*A^{-1}B\succ0.\] System block removal \(M(x,y)^T=(f,g)^T\) produces \[S_Dy=g-CA^{-1}f,\qquad Ax=f-By.\] \section{Saddle-Point and KKT Matrices}\label{saddle-point-and-kkt-matrices} \index{saddle-point and kkt matrices@Saddle-Point and KKT Matrices} \[K=\begin{pmatrix}H&A^*\\A&0\end{pmatrix}.\] \(H=H^*\),\(K\) is Hermitian but generally indefinite. \(H\succ0\) and \(A\) has full rank for rows, \(K\) is not unusual. Schur's complement is' \[S=-AH^{-1}A^*\prec0.\] \bookmarksetup{startatroot} \chapter{LU Factorization of Rectangular Matrices}\label{lu-factorization-of-rectangular-matrices} \index{lu factorization of rectangular matrices@LU Factorization of Rectangular Matrices} Both \[A\in\mathbb{K}^{m\times n}.\] \section{LU without Pivoting}\label{lu-without-pivoting} \index{lu without pivoting@LU without Pivoting} When gaussiane eliminations can be performed without row exchanges, a rectangular matrix admits a factorization of the type \[A=LU.\] \(m\ge n\): \[L\in\mathbb{K}^{m\times n}, \qquad U\in\mathbb{K}^{n\times n},\] with \(L\) bottom trapezoidal and \(U\) superior triangular. \(m\le n\): \[L\in\mathbb{K}^{m\times m}, \qquad U\in\mathbb{K}^{m\times n},\] with \(L\) lower triangular and \(U\) Top trapezoidal. \section{LU with Partial Pivoting}\label{lu-with-partial-pivoting} \index{lu with partial pivoting@LU with Partial Pivoting} The norm form is \[PA=LU,\] where \(P\) is a matrix of permutation of the rows. For rectangular plates: \begin{itemize} \item the partial pivoting exchange rows; \item the factorization proceeds up to \(\min(m,n)\) steps; \item the numerical rank can emerge from the presence of small or null pivot. \end{itemize} \section{LU with Full Pivoting}\label{lu-with-full-pivoting} \index{lu with full pivoting@LU with Full Pivoting} Factorization with full pivoting is \[PAQ=LU,\] where: \begin{itemize} \item \(P\) permutes the rows; \item \(Q\) permutes the columns. \end{itemize} At each step you choose as a pivot the maximum module element in the subblock still not factorized. Advantages: \begin{itemize} \item greater robustness than partial pivoting; \item useful to reveal the rank. \end{itemize} Disadvantages \begin{itemize} \item higher cost in search of pivot; \item more permutations. \end{itemize} \section{Rank-Revealing Form with Full Pivoting}\label{rank-revealing-form-with-full-pivoting} \index{rank-revealing form with full pivoting@Rank-Revealing Form with Full Pivoting} \(\mathop{\mathrm{rank}}(A)=r\), after appropriate permutations: \[PAQ= \begin{pmatrix} L_{11}\\ L_{21} \end{pmatrix} \begin{pmatrix} U_{11} & U_{12} \end{pmatrix},\] where \[L_{11}\in\mathbb{K}^{r\times r}, \qquad U_{11}\in\mathbb{K}^{r\times r}\] They are not singular. \bookmarksetup{startatroot} \chapter{Elementary Frobenius Matrices for LU}\label{elementary-frobenius-matrices-for-lu} \index{elementary frobenius matrices for lu@Elementary Frobenius Matrices for LU} An elementary Frobenius matrix associated with Gaussian elimination has the shape \[F_k=I-\ell_k e_k^T,\] where \(\ell_k\) contains the multipliers used to undo the items under the column pivot \(k\). For example: \[F_k= \begin{pmatrix} 1&&&&\\ &\ddots&&&\\ &&1&&\\ &&-\ell_{k+1,k}&1&\\ &&\vdots&&\ddots\\ &&-\ell_{n,k}&&&1 \end{pmatrix}.\] Property: \begin{itemize} \item \(F_k\) is lower triangular; \item \(\det(F_k)=1\); \item \(F_k\) is invertible; \item \[F_k^{-1}=I+\ell_k e_k^T.\] \end{itemize} Gaussian elimination can be written as \[U=F_{n-1}\cdots F_2F_1A.\] So: \[A=LU, \qquad L=F_1^{-1}F_2^{-1}\cdots F_{n-1}^{-1}.\] With pivoting: \[PA=LU.\] \bookmarksetup{startatroot} \chapter{\texorpdfstring{\(LDL^*\) Factorization}{LDL\^{}* Factorization}}\label{ldl-factorization} \index{ldl-star factorization@LDL-star Factorization} For hermitiane machines: \[A=LDL^*.\] For indefinite matrices, symmetric pivoting is used: \[P^*AP=LDL^*,\] with \(D\) diagonal blocks, typically with blocks \(1\times1\) and \(2\times2\). In the real case: \[P^TAP=LDL^T.\] It is particularly suitable for indefinite symmetric systems and KKT. \bookmarksetup{startatroot} \chapter{QR Factorization of Rectangular Matrices}\label{qr-factorization-of-rectangular-matrices} \index{qr factorization of rectangular matrices@QR Factorization of Rectangular Matrices} Both \[A\in\mathbb{K}^{m\times n}.\] \section{\texorpdfstring{Tall Matrix: \(m\ge n\)}{Tall Matrix: m\textbackslash ge n}}\label{tall-matrix-mge-n} \index{tall matrix m ge n@Tall Matrix: m ge n} \(A\) has full rank for columns: \[\mathop{\mathrm{rank}}(A)=n.\] Reduced QR: \[A=QR,\] with \[Q\in\mathbb{K}^{m\times n}, \qquad Q^*Q=I_n,\] and \[R\in\mathbb{K}^{n\times n}\] superior and not singular triangular. Full QR: \[A=\widehat Q \begin{pmatrix} R\\ 0 \end{pmatrix},\] where \[\widehat Q\in\mathbb{K}^{m\times m}\] is unitary/orthagonal. \section{\texorpdfstring{Wide Matrix: \(m\le n\)}{Wide Matrix: m\textbackslash le n}}\label{wide-matrix-mle-n} \index{wide matrix m le n@Wide Matrix: m le n} A norm QR produces: \[A=QR,\] with \[Q\in\mathbb{K}^{m\times m}, \qquad R\in\mathbb{K}^{m\times n},\] where \(R\) is superior trapezoidal. \(A\) has full rank for rows: \[\mathop{\mathrm{rank}}(A)=m.\] \section{QR with Column Pivoting}\label{qr-with-column-pivoting} \index{qr with column pivoting@QR with Column Pivoting} The shape is \[AP=QR,\] where \(P\) is a matrix of permutation of the columns. It is used for: \begin{itemize} \item improve stability; \item reveal the rank; \item deal with problems at the least squares-deficient. \end{itemize} \(\mathop{\mathrm{rank}}(A)=r\), ideally: \[AP= Q \begin{pmatrix} R_{11} & R_{12}\\ 0 & 0 \end{pmatrix},\] with \[R_{11}\in\mathbb{K}^{r\times r}\] not singular. \bookmarksetup{startatroot} \chapter{LQ, RRQR, and COD Factorizations}\label{lq-rrqr-and-cod-factorizations} \index{lq rrqr and cod factorizations@LQ, RRQR, and COD Factorizations} \section{LQ Factorization}\label{lq-factorization} \index{lq factorization@LQ Factorization} For \(A\in\mathbb{K}^{m\times n}\) with \(m\le n\): \[A=LQ.\] \(A\) has full rank for rows, in reduced form \(L\in\mathbb{K}^{m\times m}\) is not unusual and lower triangular \(Q_1Q_1^*=I_m\). LQ gets by applying QR to \(A^*\). \section{Rank-Revealing QR}\label{rank-revealing-qr} \index{rank-revealing qr@Rank-Revealing QR} \[AP=QR=Q\begin{pmatrix}R_{11}&R_{12}\\0&R_{22}\end{pmatrix}.\] For numerical rank \(r\), good RRQR makes \(R_{11}\in\mathbb{K}^{r\times r}\) well conditioned and \(R_{22}\) Baby. \section{Complete Orthogonal Decomposition}\label{complete-orthogonal-decomposition} \index{complete orthogonal decomposition@Complete Orthogonal Decomposition} For \(\mathop{\mathrm{rank}}(A)=r\): \[A=Q\begin{pmatrix}T&0\\0&0\end{pmatrix}Z^*,\] with \(Q,Z\) Units and \(T\in\mathbb{K}^{r\times r}\) triangular not singular. It is useful for numerical rank, least squares-deficient and minimum-norm solutions. \bookmarksetup{startatroot} \chapter{SVD: Forms and Advanced Properties}\label{svd-forms-and-advanced-properties} \index{svd forms and advanced properties@SVD: Forms and Advanced Properties} Both \(A\in\mathbb{K}^{m\times n}\), \(\mathop{\mathrm{rank}}(A)=r\). Complete SVD: \[A=U\Sigma V^*.\] SVD compact: \[A=U_r\Sigma_rV_r^*,\qquad \Sigma_r=\mathop{\mathrm{diag}}(\sigma_1,\dots,\sigma_r),\quad \sigma_r>0.\] From SVD: \[\mathop{\mathrm{range}}(A)=\operatorname{span}(u_1,\dots,u_r),\qquad \ker(A^*)=\operatorname{span}(u_{r+1},\dots,u_m),\] \[\mathop{\mathrm{range}}(A^*)=\operatorname{span}(v_1,\dots,v_r),\qquad \ker(A)=\operatorname{span}(v_{r+1},\dots,v_n).\] The pseudoinverse is \[A^\dagger=V_r\Sigma_r^{-1}U_r^*.\] \section{Eckart--Young--Mirsky Theorem}\label{eckartyoungmirsky-theorem} \index{eckart-young-mirsky theorem@Eckart–Young–Mirsky Theorem} For \(k{\raggedright\arraybackslash}p{(\linewidth - 6\tabcolsep) * \real{0.2500}} >{\raggedright\arraybackslash}p{(\linewidth - 6\tabcolsep) * \real{0.2500}} >{\raggedright\arraybackslash}p{(\linewidth - 6\tabcolsep) * \real{0.2500}} >{\raggedright\arraybackslash}p{(\linewidth - 6\tabcolsep) * \real{0.2500}}@{}} \toprule\noalign{} \begin{minipage}[b]{\linewidth}\raggedright \textbf{Factorization} \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright \textbf{matrix} \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright \textbf{Form} \end{minipage} & \begin{minipage}[b]{\linewidth}\raggedright \textbf{Use} \end{minipage} \\ \midrule\noalign{} \endhead \bottomrule\noalign{} \endlastfoot L & General & \(PAQ=LU\) & systems, elimination, rank \\ Cholesky & SPD/HPD & \(A=LL^*\) & positive defined systems \\ \(LDL^*\) & Hermitian & \(P^*AP=LDL^*\) & indefinite, KKT \\ QR & above all \(m\ge n\) & \(A=QR\) & least squares \\ L & above all \(m\le n\) & \(A=LQ\) & minimum-norm \\ RRQR & General & \(AP=QR\) & numerical rank \\ COD & General & \(A=Q\begin{psmallmatrix}T&0\\0&0\end{psmallmatrix}Z^*\) & deficient rank \\ SVD & General & \(A=U\Sigma V^*\) & rank, pseudoinverse, LS \\ Schur & square & \(A=QTQ^*\) & eigenvalues \\ Jordan & square & \(A=VJV^{-1}\) & theory \\ \end{longtable} } \bookmarksetup{startatroot} \chapter{Generalized Inverses and the Pseudoinverse}\label{generalized-inverses-and-the-pseudoinverse} \index{generalized inverses and the pseudoinverse@Generalized Inverses and the Pseudoinverse} \section{Left Inverse}\label{left-inverse} \index{left inverse@Left Inverse} For \[A\in\mathbb{K}^{m\times n}, \qquad m\ge n,\] a matrix \[L\in\mathbb{K}^{n\times m}\] is a left inverse if \[LA=I_n.\] It exists if and only if: \[\mathop{\mathrm{rank}}(A)=n.\] A canonical choice: \[L=(A^*A)^{-1}A^*.\] \section{Right Inverse}\label{right-inverse} \index{right inverse@Right Inverse} For \[A\in\mathbb{K}^{m\times n}, \qquad m\le n,\] a matrix \[R\in\mathbb{K}^{n\times m}\] is a right inverse if \[AR=I_m.\] It exists if and only if: \[\mathop{\mathrm{rank}}(A)=m.\] A canonical choice: \[R=A^*(AA^*)^{-1}.\] \section{Generalized Inverse}\label{generalized-inverse} \index{generalized inverse@Generalized Inverse} A matrix \(G\) is a generalized inverse of \(A\) if \[AGA=A.\] In general it is not unique. \section{Moore--Penrose Pseudoinverse}\label{moorepenrose-pseudoinverse} \index{moore-penrose pseudoinverse@Moore–Penrose Pseudoinverse} Moore's pseudoinverse--Penrose \[A\in\mathbb{K}^{m\times n}\] is the only matrix \[A^\dagger\in\mathbb{K}^{n\times m}\] that satisfies: \[AA^\dagger A=A,\] \[A^\dagger AA^\dagger=A^\dagger,\] \[(AA^\dagger)^*=AA^\dagger,\] \[(A^\dagger A)^*=A^\dagger A.\] \subsection{Minimum Properties}\label{minimum-properties} \index{minimum properties@Minimum Properties} For every \(b\in\mathbb{K}^m\), the vector \[x^\dagger=A^\dagger b\] is the unique minimum-Euclidean-norm least-squares solution: \[x^\dagger =\mathop{\mathrm{argmin}}_{x} \left\{\|x\|_2: x\in\mathop{\mathrm{argmin}}_{z}\|Az-b\|_2\right\}.\] In particular, if \(Ax=b\) is consistent, then \(A^\dagger b\) is the unique solution of minimum norm. Moreover, \[AA^\dagger b =\mathop{\mathrm{argmin}}_{y\in\mathop{\mathrm{range}}(A)} \|b-y\|_2,\] and the minimum residual is orthogonal to the range of \(A\): \[b-AA^\dagger b\in\ker(A^*).\] Among all generalized inverses \(G\) satisfying \(AGA=A\), the Moore--Penrose pseudoinverse is the unique one with minimum Frobenius norm: \[A^\dagger =\mathop{\mathrm{argmin}}_{G:\,AGA=A}\|G\|_F.\] If \(A\) has full row rank, \(A^\dagger\) is the minimum-Frobenius-norm right inverse; if \(A\) has full column rank, it is the minimum-Frobenius-norm left inverse. \section{Pseudoinverse via the SVD}\label{pseudoinverse-via-the-svd} \index{pseudoinverse via the svd@Pseudoinverse via the SVD} \[A=U\Sigma V^*,\] then \[A^\dagger=V\Sigma^\dagger U^*,\] where \[\Sigma^\dagger\] you get inverting only the singular values not null. \[\Sigma=\mathop{\mathrm{diag}}(\sigma_1,\dots,\sigma_r,0,\dots),\] then \[\Sigma^\dagger= \mathop{\mathrm{diag}}\left( \frac1{\sigma_1}, \dots, \frac1{\sigma_r}, 0,\dots \right)\] with the transposed dimensions. \section{Pseudoinverse via Two QR Factorizations}\label{pseudoinverse-via-two-qr-factorizations} \index{pseudoinverse via two qr factorizations@Pseudoinverse via Two QR Factorizations} Let \(A\in\mathbb{K}^{m\times n}\) have rank \(r\). First compute a rank-revealing QR factorization with column pivoting and retain only the nonzero part: \[A\Pi=Q_1R,\] where \(Q_1\in\mathbb{K}^{m\times r}\) has orthonormal columns and \(R\in\mathbb{K}^{r\times n}\) has full row rank. Then compute a thin QR factorization of \(R^*\): \[R^*=ZT,\] where \(Z\in\mathbb{K}^{n\times r}\) has orthonormal columns and \(T\in\mathbb{K}^{r\times r}\) is nonsingular and upper triangular. Since \(R=T^*Z^*\), \[R^\dagger=ZT^{-*},\] and therefore \[\boxed{A^\dagger=\Pi ZT^{-*}Q_1^*.}\] No inverse needs to be formed explicitly: solve the triangular system \[T^*Y=Q_1^*\] and assemble \(A^\dagger=\Pi ZY\). Thus a general rank-\(r\) pseudoinverse can be computed with two QR factorizations and triangular solves, without forming the normal equations. \section{Special Cases}\label{special-cases} \index{special cases@Special Cases} \(A\) is square and invertible: \[A^\dagger=A^{-1}.\] \(A\) has full rank for columns: \[A^\dagger=(A^*A)^{-1}A^*.\] \(A\) has full rank for rows: \[A^\dagger=A^*(AA^*)^{-1}.\] \section{Projectors Associated with the Pseudoinverse}\label{projectors-associated-with-the-pseudoinverse} \index{projectors associated with the pseudoinverse@Projectors Associated with the Pseudoinverse} \[AA^\dagger\] is the orthogonal projector on \[\mathop{\mathrm{range}}(A).\] \[A^\dagger A\] is the orthogonal projector on \[\mathop{\mathrm{range}}(A^*)=(\ker A)^\perp.\] \[I-AA^\dagger\] is the orthogonal projector on \[\ker(A^*).\] \[I-A^\dagger A\] is the orthogonal projector on \[\ker(A).\] \section{Least Squares and the Pseudoinverse}\label{least-squares-and-the-pseudoinverse} \index{least squares and the pseudoinverse@Least Squares and the Pseudoinverse} The minimum norm solution of the problem \[\min_x\|Ax-b\|_2\] is: \[x^\dagger=A^\dagger b.\] All solutions at the smallest squares are: \[x=A^\dagger b+(I-A^\dagger A)z, \qquad z\in\mathbb{K}^n.\] The minimum residue is: \[r_\star=b-AA^\dagger b.\] Projection \(b\) up \(\mathop{\mathrm{range}}(A)\) is: \[AA^\dagger b.\] \bookmarksetup{startatroot} \chapter{Pseudoinverse: Identities and Decompositions}\label{pseudoinverse-identities-and-decompositions} \index{pseudoinverse identities and decompositions@Pseudoinverse: Identities and Decompositions} In addition to Moore--Penrose conditions: \[(A^\dagger)^\dagger=A,\qquad (A^*)^\dagger=(A^\dagger)^*,\] \[\mathop{\mathrm{range}}(A^\dagger)=\mathop{\mathrm{range}}(A^*),\qquad \ker(A^\dagger)=\ker(A^*).\] In general: \[(AB)^\dagger e B^\dagger A^\dagger.\] The matrices \[AA^\dagger,\qquad A^\dagger A\] are respectively the orthogonal projectors on \(\mathop{\mathrm{range}}(A)\) and \(\mathop{\mathrm{range}}(A^*)\). \bookmarksetup{startatroot} \chapter{Least-Squares Problems}\label{least-squares-problems} \index{least-squares problems@Least-Squares Problems} Both \[A\in\mathbb{K}^{m\times n}, \qquad b\in\mathbb{K}^m.\] The problem at the least squares is \[\min_{x\in\mathbb{K}^n}\|Ax-b\|_2.\] \section{Normal Equations}\label{normal-equations} \index{normal equations@Normal Equations} Every solution to the least squares meets: \[A^*(Ax-b)=0,\] i.e. \[A^*Ax=A^*b.\] Geometric interpretation: \[Ax\] is the orthogonal projection of \(b\) up \[\mathop{\mathrm{range}}(A).\] \section{Tall Full-Column-Rank Case}\label{tall-full-column-rank-case} \index{tall full-column-rank case@Tall Full-Column-Rank Case} \[m\ge n, \qquad \mathop{\mathrm{rank}}(A)=n,\] the solution to the least squares is unique: \[x=(A^*A)^{-1}A^*b.\] Using reduced QR: \[A=QR,\] you have \[Rx=Q^*b.\] \section{Tall Rank-Deficient Case}\label{tall-rank-deficient-case} \index{tall rank-deficient case@Tall Rank-Deficient Case} \[m\ge n, \qquad \mathop{\mathrm{rank}}(A)=r