Gramian matrix

Short description: Matrix of inner products of a set of vectors

In linear algebra, the Gram matrix (or Gramian matrix, Gramian) of a set of vectors v1,…,vn in an inner product space is the Hermitian matrix of inner products, whose entries are given by Gij=⟨vi,vj⟩.[1]

An important application is to compute linear independence: a set of vectors are linearly independent if and only if the Gram determinant (the determinant of the Gram matrix) is non-zero.

It is named after Jørgen Pedersen Gram.

## Contents

* 1 Examples
* 1.1 Applications
* 2 Properties
* 2.1 Positive-semidefiniteness
* 2.2 Finding a vector realization
* 2.3 Uniqueness of vector realizations
* 2.4 Other properties
* 3 Gram determinant
* 4 See also
* 5 References
* 6 External links

## Examples

For finite-dimensional real vectors in ℝn with the usual Euclidean dot product, the Gram matrix is simply G=VTV, where V is a matrix whose columns are the vectors vk. For complex vectors in ℂn, G=VHV, where VH is the conjugate transpose of V.

Given square-integrable functions {ℓi(⋅),i=1,…,n} on the interval [t0,tf], the Gram matrix G=[Gij] is:

Gij=∫t0tfℓi(τ)ℓj¯(τ)dτ.

For any bilinear form B on a finite-dimensional vector space over any field we can define a Gram matrix G attached to a set of vectors v1,…,vn by Gij=B(vi,vj). The matrix will be symmetric if the bilinear form B is symmetric.

### Applications

* In Riemannian geometry, given an embedded k-dimensional Riemannian manifold M⊂ℝn and a coordinate chart ϕ:U->M for (x1,…,xk)∈U⊂ℝk, the volume form ω on M induced by the embedding may be computed using the Gramian of the coordinate tangent vectors:

ω=det⁡G dx1⋯dxk,G=[⟨∂ϕ∂xi,∂ϕ∂xj⟩].

This generalizes the classical surface integral of a parametrized surface ϕ:U->S⊂ℝ3 for (x,y)∈U⊂ℝ2:

∫Sf dA = ∬Uf(ϕ(x,y))|∂ϕ∂x×∂ϕ∂y|dxdy.

* If the vectors are centered random variables, the Gramian is approximately proportional to the covariance matrix, with the scaling determined by the number of elements in the vector.
* In quantum chemistry, the Gram matrix of a set of basis vectors is the overlap matrix.
* In control theory (or more generally systems theory), the controllability Gramian and observability Gramian determine properties of a linear system.
* Gramian matrices arise in covariance structure model fitting (see e.g., Jamshidian and Bentler, 1993, Applied Psychological Measurement, Volume 18, pp. 79–94).
* In the finite element method, the Gram matrix arises from approximating a function from a finite dimensional space; the Gram matrix entries are then the inner products of the basis functions of the finite dimensional subspace.
* In machine learning, kernel functions are often represented as Gram matrices.[2]
* Since the Gram matrix over the reals is a symmetric matrix, it is diagonalizable and its eigenvalues are non-negative. The diagonalization of the Gram matrix is the singular value decomposition.

## Properties

### Positive-semidefiniteness

The Gram matrix is symmetric in the case the real product is real-valued; it is Hermitian in the general, complex case by definition of an inner product.

The Gram matrix is positive semidefinite, and every positive semidefinite matrix is the Gramian matrix for some set of vectors. The fact that the Gramian matrix is positive-semidefinite can be seen from the following simple derivation:

xT𝐆x=∑i,jxixj⟨vi,vj⟩=∑i,j⟨xivi,xjvj⟩=⟨∑ixivi,∑jxjvj⟩=‖∑ixivi‖2≥0.

The first equality follows from the definition of matrix multiplication, the second and third from the bi-linearity of the inner-product, and the last from the positive definiteness of the inner product. Note that this also shows that the Gramian matrix is positive definite if and only if the vectors vi are linearly independent (that is, ∑ixivi≠0 for all x).[1]

### Finding a vector realization

Given any positive semidefinite matrix M, one can be decompose it as:

M=B*B,

where B* is the conjugate transpose of B (or M=BTB in the real case). Here B is a k×n matrix, where k is the rank of M. Various ways to obtain such a decomposition include computing the Cholesky decomposition or taking the non-negative square root of M.

The columns b(1),…,b(n) of B can be seen as n vectors in ℂk (or k-dimensional Euclidean space ℝk, in the real case). Then

Mij=b(i)⋅b(j)

where the dot product a⋅b=∑ℓ=1kaℓ‾bℓ is the usual inner product on ℂk.

Thus a Hermitian matrix M is positive semidefinite if and only if it is the Gram matrix of some vectors b(1),…,b(n). Such vectors are called a vector realization of M. The infinite-dimensional analog of this statement is Mercer's theorem.

### Uniqueness of vector realizations

If M is the Gram matrix of vectors v1,…,vn in ℝk, then applying any rotation or reflection of ℝk (any orthogonal transformation, that is, any Euclidean isometry preserving 0) to the sequence of vectors results in the same Gram matrix. That is, for any k×k orthogonal matrix Q, the Gram matrix of Qv1,…,Qvn is also M.

This is the only way in which two real vector realizations of M can differ: the vectors v1,…,vn are unique up to orthogonal transformations. In other words, the dot products vi⋅vj and wi⋅wj are equal if and only if some rigid transformation of ℝk transforms the vectors v1,…,vn to w1,…,wn and 0 to 0.

The same holds in the complex case, with unitary transformations in place of orthogonal ones. That is, if the Gram matrix of vectors v1,…,vn is equal to the Gram matrix of vectors w1,…,wn in ℂk, then there is a unitary k×k matrix U (meaning U*U=I) such that vi=Uwi for i=1,…,n.[3]

### Other properties

* The Gram matrix of any orthonormal basis is the identity matrix.
* The rank of the Gram matrix of vectors in ℝk or ℂk equals the dimension of the space spanned by these vectors.[1]

## Gram determinant

The Gram determinant or Gramian is the determinant of the Gram matrix:

G(x1,…,xn)=|⟨x1,x1⟩⟨x1,x2⟩…⟨x1,xn⟩⟨x2,x1⟩⟨x2,x2⟩…⟨x2,xn⟩⋮⋮⋱⋮⟨xn,x1⟩⟨xn,x2⟩…⟨xn,xn⟩|.

If x1,⋯,xn are vectors in ℝn, then it is the square of the n-dimensional volume of the parallelotope formed by the vectors. In particular, the vectors are linearly independent if and only if the parallelotope has nonzero n-dimensional volume, if and only if Gram determinant is nonzero, if and only if the Gram matrix is nonsingular.

The Gram determinant can also be expressed in terms of the exterior product of vectors by

G(x1,…,xn)=‖x1∧⋯∧xn‖2.

## See also

* Controllability Gramian
* Observability Gramian

## References

1. ↑ 1.0 1.1 1.2 Horn & Johnson 2013, p. 441, p.441, Theorem 7.2.10
2. ↑ Lanckriet, G. R. G.; Cristianini, N.; Bartlett, P.; Ghaoui, L. E.; Jordan, M. I. (2004). "Learning the kernel matrix with semidefinite programming". Journal of Machine Learning Research 5: 27–72 [p. 29]. https://dl.acm.org/citation.cfm?id=894170.
3. ↑ (Horn Johnson), p. 452, Theorem 7.3.11

* Horn, Roger A.; Johnson, Charles R. (2013). Matrix Analysis (2nd ed.). Cambridge University Press. ISBN 978-0-521-54823-6.

## External links

* Hazewinkel, Michiel, ed. (2001), "Gram matrix", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=p/g044750
* Volumes of parallelograms by Frank Jones

* v
* t
* e

Matrix classes

Explicitly constrained entries|

* (0,1)
* Alternant
* Anti-diagonal
* Anti-Hermitian
* Anti-symmetric
* Arrowhead
* Band
* Bidiagonal
* Binary
* Bisymmetric
* Block-diagonal
* Block
* Block tridiagonal
* Boolean
* Cauchy
* Centrosymmetric
* Conference
* Complex Hadamard
* Copositive
* Diagonally dominant
* Diagonal
* Discrete Fourier Transform
* Elementary
* Equivalent
* Frobenius
* Generalized permutation
* Hadamard
* Hankel
* Hermitian
* Hessenberg
* Hollow
* Integer
* Logical
* Markov
* Metzler
* Monomial
* Moore
* Nonnegative
* Partitioned
* Parisi
* Pentadiagonal
* Permutation
* Persymmetric
* Polynomial
* Positive
* Quaternionic
* Sign
* Signature
* Skew-Hermitian
* Skew-symmetric
* Skyline
* Sparse
* Sylvester
* Symmetric
* Toeplitz
* Triangular
* Tridiagonal
* Unitary
* Vandermonde
* Walsh
* Z

Constant|

* Exchange
* Hilbert
* Identity
* Lehmer
* Of ones
* Pascal
* Pauli
* Redheffer
* Shift
* Zero

Conditions on eigenvalues or eigenvectors|

* Companion
* Convergent
* Defective
* Diagonalizable
* Hurwitz
* Positive-definite
* Stability
* Stieltjes

Satisfying conditions on products or inverses|

* Congruent
* Idempotent or Projection
* Invertible
* Involutory
* Nilpotent
* Normal
* Orthogonal
* Orthonormal
* Singular
* Unimodular
* Unipotent
* Totally unimodular
* Weighing

With specific applications|

* Adjugate
* Alternating sign
* Augmented
* Bézout
* Carleman
* Cartan
* Circulant
* Cofactor
* Commutation
* Confusion
* Coxeter
* Derogatory
* Distance
* Duplication
* Elimination
* Euclidean distance
* Fundamental (linear differential equation)
* Generator
* Gramian
* Hessian
* Householder
* Jacobian
* Moment
* Payoff
* Pick
* Random
* Rotation
* Seifert
* Shear
* Similarity
* Symplectic
* Totally positive
* Transformation
* Wedderburn
* X–Y–Z

Used in statistics|

* Bernoulli
* Centering
* Correlation
* Covariance
* Design
* Dispersion
* Doubly stochastic
* Fisher information
* Hat
* Precision
* Stochastic
* Transition

Used in graph theory|

* Adjacency
* Biadjacency
* Degree
* Edmonds
* Incidence
* Laplacian
* Seidel adjacency
* Skew-adjacency
* Tutte

Used in science and engineering|

* Cabibbo–Kobayashi–Maskawa
* Density
* Fundamental (computer vision)
* Fuzzy associative
* Gamma
* Gell-Mann
* Hamiltonian
* Irregular
* Overlap
* S
* State transition
* Substitution
* Z (chemistry)

Related terms|

* Jordan canonical form
* Linear independence
* Matrix exponential
* Matrix representation of conic sections
* Perfect matrix
* Pseudoinverse
* Quaternionic matrix
* Row echelon form
* Wronskian

* List of matrices
* Category:Matrices

0.00

(0 votes)

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Gramian_matrix&oldid=178367"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template