Matrix norm

In mathematics, a matrix norm is a vector norm in a vector space whose elements (vectors) are matrices (of given dimensions).
Definition.
Given a field formula_1 of either real or complex numbers, and the vector space formula_2 of all matrices of size formula_3 (with formula_4 rows and formula_5 columns) with entries in the field formula_1, a matrix norm is a norm on the vector space formula_2 (with individual norms denoted using double vertical bars such as formula_8). Thus, the matrix norm is a function formula_9 that must satisfy the following properties:
For all scalars formula_10 and for all matrices formula_11,
Additionally, in the case of square matrices (matrices with ), some (but not all) matrix norms satisfy the following condition, which is related to the fact that matrices are more than just vectors:
A matrix norm that satisfies this additional property is called a submultiplicative norm (in some books, the terminology "matrix norm" is used only for those norms which are submultiplicative). The set of all formula_20 matrices, together with such a submultiplicative norm, is an example of a Banach algebra.
The definition of submultiplicativity is sometimes extended to non-square matrices, as in the case of the induced "p"-norm, where for formula_21 and formula_22 holds that formula_23. Here, formula_24 and formula_25 are the norms induced from formula_26 and formula_27, respectively, where .
There are three types of matrix norms which will be discussed below:
Matrix norms induced by vector norms.
Suppose a vector norm formula_28 on formula_29 is given. Any formula_3 matrix induces a linear operator from formula_31 to formula_29 with respect to the standard basis, and one defines the corresponding "induced norm" or "operator norm" on the space formula_2 of all formula_3 matrices as follows:
In particular, if the "p"-norm for vectors () is used for both spaces formula_31 and formula_29, then the corresponding induced operator norm is:
These induced norms are different from the "entrywise" "p"-norms and the Schatten "p"-norms for matrices treated below, which are also usually denoted by formula_39
Any induced operator norm is a submultiplicative matrix norm: formula_51 this follows from
and
Moreover, any induced norm satisfies the inequality
for all positive integers "r", where is the spectral radius of . For symmetric or hermitian , we have equality in () for the 2-norm, since in this case the 2-norm "is" precisely the spectral radius of . For an arbitrary matrix, we may not have equality for any norm; a counterexample would be
which has vanishing spectral radius. In any case, for square matrices we have the spectral radius formula:
Special cases.
In the special cases of formula_57 the induced matrix norms can be computed or estimated by
which is simply the maximum absolute column sum of the matrix;
which is simply the maximum absolute row sum of the matrix;
where formula_61 represents the largest singular value of matrix formula_17. There is an important inequality for the case formula_63:
where formula_65 is the Frobenius norm. Equality holds if and only if the matrix formula_17 is a rank-one matrix or a zero matrix. This inequality can be derived from the fact that the trace of a matrix is equal to the sum of its eigenvalues.
When formula_63 we have an equivalent definition for formula_68 as formula_69. It can be shown to be equivalent to the above definitions using the Cauchy–Schwarz inequality.
For example, for
we have that
In the special case of formula_73 (the Euclidean norm or formula_74-norm for vectors), the induced matrix norm is the "spectral norm". The spectral norm of a matrix formula_17 is the largest singular value of formula_17 (i.e., the square root of the largest eigenvalue of the matrix formula_77, where formula_78 denotes the conjugate transpose of formula_17):
In this case, formula_81 since formula_82 and similarly formula_83 by singular value decomposition (SVD).
"Entrywise" matrix norms.
These norms treat an formula_84 matrix as a vector of size formula_85, and use one of the familiar vector norms. For example, using the "p"-norm for vectors, , we get:
This is a different norm from the induced "p"-norm (see above) and the Schatten "p"-norm (see below), but the notation is the same.
The special case "p" = 2 is the Frobenius norm, and "p" = ∞ yields the maximum norm.
and norms.
Let formula_87 be the columns of matrix formula_17. The formula_89 norm is the sum of the Euclidean norms of the columns of the matrix:
The formula_89 norm as an error function is more robust, since the error for each data point (a column) is not squared. It is used in robust data analysis and sparse coding.
For , the formula_89 norm can be generalized to the formula_93 norm as follows:
Frobenius norm.
When for the formula_93 norm, it is called the Frobenius norm or the Hilbert–Schmidt norm, though the latter term is used more frequently in the context of operators on (possibly infinite-dimensional) Hilbert space. This norm can be defined in various ways:
where formula_97 are the singular values of formula_17. Recall that the trace function returns the sum of diagonal entries of a square matrix.
The Frobenius norm is an extension of the Euclidean norm to formula_99 and comes from the Frobenius inner product on the space of all matrices.
The Frobenius norm is submultiplicative and is very useful for numerical linear algebra. The submultiplicativity of Frobenius norm can be proved using Cauchy–Schwarz inequality.
Frobenius norm is often easier to compute than induced norms, and has the useful property of being invariant under rotations (and unitary operations in general). That is, formula_100 for any unitary matrix formula_101. This property follows from the cyclic nature of the trace (formula_102):
and analogously:
where we have used the unitary nature of formula_101 (that is, formula_106).
It also satisfies
and 
where formula_109 is the Frobenius inner product.
Max norm.
The max norm is the elementwise norm with "p" = "q" = ∞:
This norm is not submultiplicative.
Note that in some literature (such as Communication complexity), an alternative definition of max-norm, also called the formula_111-norm, refers to the factorization norm:
Schatten norms.
The Schatten "p"-norms arise when applying the "p"-norm to the vector of singular values of a matrix. If the singular values of the formula_3 matrix formula_17 are denoted by "σi", then the Schatten "p"-norm is defined by
These norms again share the notation with the induced and entrywise "p"-norms, but they are different.
All Schatten norms are submultiplicative. They are also unitarily invariant, which means that formula_116 for all matrices formula_17 and all unitary matrices formula_101 and formula_119.
The most familiar cases are "p" = 1, 2, ∞. The case "p" = 2 yields the Frobenius norm, introduced before. The case "p" = ∞ yields the spectral norm, which is the operator norm induced by the vector 2-norm (see above). Finally, "p" = 1 yields the nuclear norm (also known as the "trace norm", or the Ky Fan 'n'-norm), defined as
where formula_121 denotes a positive semidefinite matrix formula_18 such that formula_123. More precisely, since formula_77 is a positive semidefinite matrix, its square root is well-defined. The nuclear norm formula_125 is a convex envelope of the rank function formula_126, so it is often used in mathematical optimization to search for low rank matrices.
Consistent norms.
A matrix norm formula_127 on formula_2 is called "consistent" with a vector norm formula_129 on formula_31 and a vector norm formula_131 on formula_29, if:
for all formula_134. All induced norms are consistent by definition.
Compatible norms.
A matrix norm formula_135 on formula_99 is called "compatible" with a vector norm formula_137 on formula_31, if:
for all formula_140. 
Induced norms are compatible with the inducing vector norm by definition. Also, any submultiplicative matrix norm on formula_141 induces a vector norm on formula_142 with which it is compatible, simply by defining formula_143.
Monotone norms.
A matrix norm formula_135 is called "monotone" if it is monotonic with respect to the Loewner order. Thus, a matrix norm is increasing if
The Frobenius norm and spectral norm are examples of monotone norms.
Equivalence of norms.
For any two matrix norms formula_146 and formula_147, we have that:
for some positive numbers "r" and "s", for all matrices formula_149. In other words, all norms on formula_2 are "equivalent"; they induce the same topology on formula_2. This is true because the vector space formula_2 has the finite dimension formula_3.
Moreover, for every vector norm formula_28 on formula_155, there exists a unique positive real number formula_156 such that formula_157 is a submultiplicative matrix norm for every formula_158.
A submultiplicative matrix norm formula_146 is said to be "minimal", if there exists no other submultiplicative matrix norm formula_147 satisfying formula_161.
Examples of norm equivalence.
Let formula_162 once again refer to the norm induced by the vector "p"-norm (as above in the Induced Norm section).
For matrix formula_163 of rank formula_164, the following inequalities hold:
Another useful inequality between matrix norms is
which is a special case of Hölder's inequality.