A vector norm measures the size, or length, of a vector. For complex 
with equality if and only if
(nonnegativity),
for all
(homogeneity),
for all
(the triangle inequality).
An important class of norms is the Hölder 
The 
Other important special cases are
A useful concept is that of the dual norm associated with a given vector norm, which is defined by
The maximum is attained because the definition is equivalent to 
We can rewrite the definition of dual norm, using the homogeneity of vector norms, as
Hence we have the attainable inequality
which is the generalized Hölder inequality.
The dual of the 
An important special case is the Cauchy–Schwarz inequality,
The notation 
In numerical linear algebra, vector norms play a crucial role in the definition of a subordinate matrix norm, as we will explain in the next post in this series.
All norms on 
For example, it is easy to see that
The 2-norm is invariant under unitary transformations: if 
Care must be taken to avoid overflow and (damaging) underflow when evaluating a vector 
References
This is a minimal set of references, which contain further useful references within.
- Takeyuki Harayama, Shuhei Kudo, Daichi Mukunoki, Toshiyuki Imamura, and Daisuke Takahashi, A Rapid Euclidean Norm Calculation Algorithm that Reduces Overflow and Underflow, in Computational Science and Its Applications–ICCSA 2021, O. Gervasi et al., eds, 95–110, Springer, 2021.
- Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, second edition, Society for Industrial and Applied Mathematics,
- Roger A. Horn and Charles R. Johnson, Matrix Analysis, second edition, Cambridge University Press, 2013. My review of the second edition.
Note: This article was revised on October 12, 2021 to change the definition of dual norm to use 
This article is part of the “What Is” series, available from https://nhigham.com/category/what-is and in PDF form from the GitHub repository https://github.com/higham/what-is.
, and future exascale computer systems will be able to tackle even larger problems. Rounding error analysis shows that the computed solution satisfies a componentwise backward error bound that, under favorable assumptions, is of order 
, where 
is the unit roundoff of the floating-point arithmetic: 
for double precision and 
for single precision. This backward error bound cannot guarantee any stability for single precision solution of today’s largest problems and suggests a loss of half the digits in the backward error for double precision.
for 
for both half precision formats, suggesting a potentially complete loss of numerical stability. Yet inner products with 
of two 
can computed as
and 
is the block size. The inner product has been broken into 
, which are computed independently then summed. Many linear algebra algorithms are blocked in an analogous way, where the blocking is into submatrices with 
or 
, so blocking brings a substantial reduction in the error bounds.
. By computing the sum 
with a more accurate summation method the error constant is further reduced to 
(this is the FABsum method of Blanchard et al. (2020)).
rather than 
for double precision, giving error bounds smaller by a factor up to 
.
with one rounding error instead of two. This results in a reduction in error bounds by a factor 
, with matrices 
of fixed size, are available on Google tensor processing units, NVIDIA GPUs, and in the ARMv8-A architecture. For half precision inputs these devices can produce results of single precision quality, which can give a significant boost in accuracy when block FMAs are chained together to form a matrix product of arbitrary dimension.
when a corresponding worst-case bound is proportional to 
, which is a significant reduction. Block FMAs and extended precision registers provide further reductions.
solved in single precision with a block size of 
versus 
graph incidence matrices and 
Bernoulli matrices. The questions of interest range from identifying structures in the spectra of particular classes of Bohemian matrix to searching for most ill conditioned matrices within a class, and applications include stress-testing algorithms and software. This minisymposium will report recent theoretical and computational progress as well as open questions.
is totally positive if every minor is positive. It is totally nonnegative if every minor is nonnegative. These definitions require, in particular, that all the matrix elements must be nonnegative or positive, as must 
.
are totally nonnegative then so is 
.![\alpha = [\alpha_1,\alpha_2,\dots,\alpha_k]](https://s0.wp.com/latex.php?latex=%5Calpha+%3D+%5B%5Calpha_1%2C%5Calpha_2%2C%5Cdots%2C%5Calpha_k%5D&bg=ffffff&fg=222222&s=0&c=20201002)
is an index vector of order 
satisfying 
. If 
and 
are index vectors of order 
, respectively, then 
denotes the 
matrix with (
) element 
.
, 
, and 
. If 
then
of order 
, (1) reduces to the well-known relation 
, while when 
, (1) reduces to the definition of matrix multiplication.
comprises the indices not in 
:
, with 
. The Hilbert matrix is a particular case of a Cauchy matrix 
, with 
for given vectors 
. A Cauchy matrix is totally positive if 
and 
, which follows from the formula
satisfy 
is defined by
with off-diagonal elements given by 
with 
, illustrated by
![A([1,2],[2,3]) = \bigl[\begin{smallmatrix} \theta & \theta \\ 1 & \theta \end{smallmatrix}\bigr]](https://s0.wp.com/latex.php?latex=A%28%5B1%2C2%5D%2C%5B2%2C3%5D%29+%3D++++%5Cbigl%5B%5Cbegin%7Bsmallmatrix%7D++++%5Ctheta+%26+%5Ctheta+%5C%5C++++1++++++%26+%5Ctheta++++%5Cend%7Bsmallmatrix%7D%5Cbigr%5D+&bg=ffffff&fg=222222&s=0&c=20201002)
has nonpositive determinant. However, the 
, with 
with all elements 
by
zero eigenvalues, which appear in a single Jordan block, and its largest eigenvalue is 
. In MATLAB, this matrix can be generated by 
bidiagonal matrix factorized into a product of elementary nonnegative bidiagonal matrices (nonnegative means that the elements of the matrix are nonnegative):
, 
, and 
are totally nonnegative, so 
is totally nonnegative by Theorem 1. With 
, we have
nonnegative bidiagonal matrix is totally nonnegative.
, where
denotes the submatrix of 
has a checkerboard (alternating) sign pattern. Indeed, we can write 
, where 
and 
has nonnegative elements, and in fact it can be shown that 
is irreducible if there does not exist a permutation matrix 
such that
and 
are square, nonempty submatrices.
. It is known that the eigenvector 
has 
sign changes, that is, 
and (
have opposite signs for 
(any zero elements are deleted before counting sign changes). Note that for 
, we already know from Perron–Frobenius theory that there is a positive eigenvector 
. This result is illustrated by the Pascal matrix above:
is totally positive for some positive integer 
totally nonnegative and the 
.
for 
, which guarantees the existence of an LU factorization. That the elements of 
and computes 
, since 
. Thus 
, 
. For 
, 
; for 
, 
. Thus 
for all 
and hence 
. But 
, so 
.
and 
will have nonnegative elements and so from the standard backward error result for LU factorization,
and hence
is a diagonal matrix with positive diagonal entries and 
and 
are unit lower and unit upper bidiagonal matrices, respectively, with the first 
entries along the subdiagonal of 
zero and the rest nonnegative.
subdiagonal entries of 
principal minors (ones based on submatrices centred on the diagonal) and 
minors in total. However, it is not necessary to check all these minors to test for total positivity.
for all index vectors ![[1,2,\dots,k]](https://s0.wp.com/latex.php?latex=%5B1%2C2%2C%5Cdots%2Ck%5D&bg=ffffff&fg=222222&s=0&c=20201002)
and the entries of the other are 
minors need to be tested. Gasca and Peña have also show that total nonnegativity can be tested by checking about 
minors. A more efficient way to test for total nonnegativity is to compute the factorization in Theorem 6 and check the signs of the entries.
the spectral radius of 
.
,
,
for any eigenvalue 
with 
.
, is called the Perron vector.
matrices. Here are some interesting cases.![A = \bigl[\begin{smallmatrix}0 & 1 \\ 0 & 0 \end{smallmatrix}\bigr]](https://s0.wp.com/latex.php?latex=A+%3D+%5Cbigl%5B%5Cbegin%7Bsmallmatrix%7D0+%26+1+%5C%5C+0+%26+0+%5Cend%7Bsmallmatrix%7D%5Cbigr%5D&bg=ffffff&fg=222222&s=0&c=20201002)
: Theorem 1 says that 
is an eigenvalue and and that it has a nonnegative eigenvector. Indeed ![[1~0]^T](https://s0.wp.com/latex.php?latex=%5B1%7E0%5D%5ET&bg=ffffff&fg=222222&s=0&c=20201002)
is an eigenvector. Note that 
is a repeated eigenvalue.![A = \bigl[\begin{smallmatrix}0 & 1 \\ 1 & 0 \end{smallmatrix}\bigr]](https://s0.wp.com/latex.php?latex=A+%3D+%5Cbigl%5B%5Cbegin%7Bsmallmatrix%7D0+%26+1+%5C%5C+1+%26+0+%5Cend%7Bsmallmatrix%7D%5Cbigr%5D&bg=ffffff&fg=222222&s=0&c=20201002)
: 
and ![[1~1]^T/2](https://s0.wp.com/latex.php?latex=%5B1%7E1%5D%5ET%2F2&bg=ffffff&fg=222222&s=0&c=20201002)
is the Perron vector for the Perron root ![A = \bigl[\begin{smallmatrix}1 & 1 \\ 1 & 1 \end{smallmatrix}\bigr]](https://s0.wp.com/latex.php?latex=A+%3D+%5Cbigl%5B%5Cbegin%7Bsmallmatrix%7D1+%26+1+%5C%5C+1+%26+1+%5Cend%7Bsmallmatrix%7D%5Cbigr%5D&bg=ffffff&fg=222222&s=0&c=20201002)
: Theorem 3 says that 
is an eigenvalue with positive eigenvector and that the other eigenvalue has modulus less than 
is an eigenvalue of ![[1~1~1]^T/3](https://s0.wp.com/latex.php?latex=%5B1%7E1%7E1%5D%5ET%2F3&bg=ffffff&fg=222222&s=0&c=20201002)
. Two of the eigenvalues are complex, however, and all three eigenvalues have modulus 1, as they must because 
, where ![e = [1,1,\dots,1]^T](https://s0.wp.com/latex.php?latex=e+%3D+%5B1%2C1%2C%5Cdots%2C1%5D%5ET&bg=ffffff&fg=222222&s=0&c=20201002)
, which means that 
. Since 
for any norm, by taking the 
then
(since 
).
. If 
and Theorem 4 says that 
. We illustrate this result in MATLAB using a scaled magic square matrix.
, as 
is the rank-
, and it is also rank-
, as in this case every column is a multiple of the vector with alternating elements 
. For 
, 
is nonsingular and the inverse is the tridiagonal (but not Toeplitz) matrix
, 
is positive definite, since every leading principal submatrix has positive determinant, as can also be seen by noting that the inverse is diagonally dominant with positive diagonal, so that 
is positive definite and hence 
, 
in this range.
, 
, we know that 
with 
for 
.
continues to hold with 
replaced by 
.
permutations 
) of the sequence 
and 
is the number of inversions in 
, that is, the number of pairs 
with 
. Each term in the sum is a signed product of 
.
, where 
denotes the 
submatrix of 
for a scalar 
. This formula is called the expansion by minors because 
is a minor of 
is triangular then 
. If 
is unitary then 
on using (3) and (4). An 
of 
. Since the eigenvalues are the roots of the characteristic polynomial 
, this relation follows by setting 
in the expression
, the determinant is
the determinant is tedious to write down. If one must compute 
is an LU factorization, with 
. As this expression indicates, the determinant is prone to overflow and underflow in floating-point arithmetic, so it may be preferable to compute 
.
is the 
element 
). More generally, Cramer’s rule says that the components of the solution to a linear system 
are given by 
, where 
denotes 
is Hadamard’s inequality. Note that for such 
, 
is real and positive (being the product of the eigenvalues, which are real and positive) and the diagonal elements are also real and positive (since 
).
or by using a QR factorization of ![A = [a_1,a_2,\dots,a_n] \in\mathbb{C}^{n\times n}](https://s0.wp.com/latex.php?latex=A+%3D+%5Ba_1%2Ca_2%2C%5Cdots%2Ca_n%5D+%5Cin%5Cmathbb%7BC%7D%5E%7Bn%5Ctimes+n%7D&bg=ffffff&fg=222222&s=0&c=20201002)
,
and obtain the analogous bound with column norms replaced by row norms.
, whose sides are the columns of 
. It might be tempting to use 
as a measure of how close a nonsingular matrix 
can be given any value by a suitable choice of 
is perfectly conditioned: 
, where 
is the condition number.
and 
if and only if the columns of 
the Hadamard condition number. In general, 
, but if 
(Higham, 2002, Prob. 14.13). Dixon (1984) shows that for classes of 
for any 
, so 
for large 
, where 
denotes the mean value. This MATLAB example illustrates these points.
term is the permanent. The permanent arises in combinatorics and quantum mechanics and is much harder to compute than the determinant: no algorithm is known for computing the permanent in 
operations for a polynomial 
, …, 
by
of degree at most 
that interpolates to the data 
, that is, 
, 
. These equations are equivalent to
![a = [a_1,a_2,\dots,a_n]^T](https://s0.wp.com/latex.php?latex=a+%3D+%5Ba_1%2Ca_2%2C%5Cdots%2Ca_n%5D%5ET&bg=ffffff&fg=222222&s=0&c=20201002)
is the vector of coefficients. This is known as the dual problem. We know from polynomial interpolation theory that there is a unique interpolant if the 
to be nonsingular.
find weights 
such that 
, 
for some 
then 
. Consequently, we have
in the 
is a constant. But 
contains a term 
(from the main diagonal), so 
. Hence
. Equating elements in the 
gives
is the Kronecker delta (equal to 
and 
takes the value 
and 
, 
. It is not hard to see that this polynomial is the Lagrange basis polynomial:
denotes the sum of all distinct products of 
(that is, 
is the 
and 
has a checkerboard sign pattern: the 
.
is a degree 
and 
.
and 
:![\notag V = \left[\begin{array}{ccccc} 1 & 1 & 1 & 1 & 1\\ 0 & \frac{1}{4} & \frac{1}{2} & \frac{3}{4} & 1\\[\smallskipamount] 0 & \frac{1}{16} & \frac{1}{4} & \frac{9}{16} & 1\\[\smallskipamount] 0 & \frac{1}{64} & \frac{1}{8} & \frac{27}{64} & 1\\[\smallskipamount] 0 & \frac{1}{256} & \frac{1}{16} & \frac{81}{256} & 1 \end{array}\right], \quad V^{-1} = \left[\begin{array}{ccccc} 1 & -\frac{25}{3} & \frac{70}{3} & -\frac{80}{3} & \frac{32}{3}\\[\smallskipamount] 0 & 16 & -\frac{208}{3} & 96 & -\frac{128}{3}\\ 0 & -12 & 76 & -128 & 64\\[\smallskipamount] 0 & \frac{16}{3} & -\frac{112}{3} & \frac{224}{3} & -\frac{128}{3}\\[\smallskipamount] 0 & -1 & \frac{22}{3} & -16 & \frac{32}{3} \end{array}\right],](https://s0.wp.com/latex.php?latex=%5Cnotag+V+%3D+%5Cleft%5B%5Cbegin%7Barray%7D%7Bccccc%7D+1+%26+1+%26+1+%26+1+%26+1%5C%5C+0+%26+%5Cfrac%7B1%7D%7B4%7D+%26+%5Cfrac%7B1%7D%7B2%7D+%26+%5Cfrac%7B3%7D%7B4%7D+%26+1%5C%5C%5B%5Csmallskipamount%5D+0+%26+%5Cfrac%7B1%7D%7B16%7D+%26+%5Cfrac%7B1%7D%7B4%7D+%26+%5Cfrac%7B9%7D%7B16%7D+%26+1%5C%5C%5B%5Csmallskipamount%5D+0+%26+%5Cfrac%7B1%7D%7B64%7D+%26+%5Cfrac%7B1%7D%7B8%7D+%26+%5Cfrac%7B27%7D%7B64%7D+%26+1%5C%5C%5B%5Csmallskipamount%5D+0+%26+%5Cfrac%7B1%7D%7B256%7D+%26+%5Cfrac%7B1%7D%7B16%7D+%26+%5Cfrac%7B81%7D%7B256%7D+%26+1+%5Cend%7Barray%7D%5Cright%5D%2C+%5Cquad+V%5E%7B-1%7D+%3D+%5Cleft%5B%5Cbegin%7Barray%7D%7Bccccc%7D+1+%26+-%5Cfrac%7B25%7D%7B3%7D+%26+%5Cfrac%7B70%7D%7B3%7D+%26+-%5Cfrac%7B80%7D%7B3%7D+%26+%5Cfrac%7B32%7D%7B3%7D%5C%5C%5B%5Csmallskipamount%5D+0+%26+16+%26+-%5Cfrac%7B208%7D%7B3%7D+%26+96+%26+-%5Cfrac%7B128%7D%7B3%7D%5C%5C+0+%26+-12+%26+76+%26+-128+%26+64%5C%5C%5B%5Csmallskipamount%5D+0+%26+%5Cfrac%7B16%7D%7B3%7D+%26+-%5Cfrac%7B112%7D%7B3%7D+%26+%5Cfrac%7B224%7D%7B3%7D+%26+-%5Cfrac%7B128%7D%7B3%7D%5C%5C%5B%5Csmallskipamount%5D+0+%26+-1+%26+%5Cfrac%7B22%7D%7B3%7D+%26+-16+%26+%5Cfrac%7B32%7D%7B3%7D+%5Cend%7Barray%7D%5Cright%5D%2C+&bg=ffffff&fg=222222&s=0&c=20201002)
.
satisfies
for all 
for all 
. It is also known that for any set of real points 
we have 
, where the lower bound is an extremely fast growing function of the dimension!
operation algorithm for solving 
of Björck and Pereyra (1970). There is now a long list of generalizations of this algorithm in various directions, including for confluent Vandermonde-like matrices (Higham, 1990), as well as for more specialized problems (Demmel and Koev, 2005) and more general ones (Bella et al., 2009). Another important observation is that the exponential lower bounds are for real nodes. For complex nodes 
can be much better conditioned. Indeed when the 
is the unitary Fourier matrix and so 
we obtain
in the case of (4)).
with 
having degree 
Nick Higham 