Algebra

The degree of some algebraic structure is some parameter that describes the structure. There is no universal definition valid for all structures, it is a per structure type thing.

This is particularly useful when talking about structures with an infinite number of elements, but it is sometimes also used for finite structures.

Examples:

the dihedral group of degree n acts on n elements, and has order 2n
the parameter $n$ that characterizes the size of the general linear group $G L (n)$ is called the degree of that group, i.e. the dimension of the underlying matrices

Finite algebraic structure

Examples:

Linear algebra

 3  0 

Linear function

The term is not very clear, as it could either mean:

a real number function whose graph is a line, i.e.:
$f (x) = a x + b$
(1)
or for higher dimensions, a hyperplane:
$f (x_{1}, x_{2}, \dots, x_{n}) = c_{1} x_{1} + c_{2} x_{2} + \dots + c_{n} x_{n} + b$
(2)
a linear map. Note that the above linear functions are not linear maps unless $b = 0$ (known as the homogeneous case), because e.g.:
$f (x + y) = a x + a y + b$
(3)
but
$f (x) + f (y) = a x + b + a y + b$
(4)
For this reason, it is better never to refer to linear maps as linear functions.

Linear map (linear operator)

A linear map is a function

f : V_{1} (F) \to V_{2} (F)

where

V_{1} (F)

and

V_{2} (F)

are two vector spaces over underlying fields

F

such that:

\forall v_{1}, v_{2} \in V_{1}, c_{1}, c_{2} \in F f (c_{1} v_{1} + c_{2} v_{2}) = c_{1} f (v_{1}) + c_{2} f (v_{2})

A common case is

F = R

V_{1} = R_{m}

and

V_{2} = R_{n}

One thing that makes such functions particularly simple is that they can be fully specified by specifyin how they act on all possible combinations of input basis vectors: they are therefore specified by only a finite number of elements of

F

Every linear map in finite dimension can be represented by a matrix, the points of the domain being represented as vectors.

As such, when we say "linear map", we can think of a generalization of matrix multiplication that makes sense in infinite dimensional spaces like Hilbert spaces, since calling such infinite dimensional maps "matrices" is stretching it a bit, since we would need to specify infinitely many rows and columns.

The prototypical building block of infinite dimensional linear map is the derivative. In that case, the vectors being operated upon are functions, which cannot therefore be specified by a finite number of parameters, e.g.

For example, the left side of the time-independent Schrödinger equation is a linear map. And the time-independent Schrödinger equation can be seen as a eigenvalue problem.

Form (mathematics)

A form is a function from a vector space to elements of the underlying field of the vector space.

Examples:

Linear form

A Linear map where the image is the underlying field of the vector space, e.g.

R^{n} \to R

The set of all linear forms over a vector space forms another vector space called the dual space.

Matrix representation of a linear form

For the typical case of a linear form over

R^{n}

, the form can be seen just as a row vector with n elements, the full form being specified by the value of each of the basis vectors.

Dual space ( $V^{*}$ )

The dual space of a vector space

V

, sometimes denoted

V^{*}

, is the vector space of all linear forms over

V

with the obvious addition and scalar multiplication operations defined.

Since a linear form is completely determined by how it acts on a basis, and since for each basis element it is specified by a scalar, at least in finite dimension, the dimension of the dual space is the same as the

V

, and so they are isomorphic because all vector spaces of the same dimension on a given field are isomorphic, and so the dual is quite a boring concept in the context of finite dimension.

Infinite dimension seems more interesting however, see: en.wikipedia.org/w/index.php?title=Dual_space&oldid=1046421278#Infinite-dimensional_case

One place where duals are different from the non-duals however is when dealing with tensors, because they transform differently than vectors from the base space

V

Dual vector ( $e^{i}$ )

Dual vectors are the members of a dual space.

In the context of tensors , we use raised indices to refer to members of the dual basis vs the underlying basis:

e_{1} e_{2} e_{3} e^{1} e^{2} e^{3} \in V \in V \in V \in V^{*} \in V^{*} \in V^{*}

The dual basis vectors

e^{i}

are defined to "pick the corresponding coordinate" out of elements of V. E.g.:

e^{1} (4, - 3, 6) e^{2} (4, - 3, 6) e^{3} (4, - 3, 6) = 4 = - 3 = 6

By expanding into the basis, we can put this more succinctly with the Kronecker delta as:

e^{i} (e_{j}) = δ_{i j}

Note that in Einstein notation, the components of a dual vector have lower indices. This works well with the upper case indices of the dual vectors, allowing us to write a dual vector

f

as:

f = f_{i} e^{i}

In the context of quantum mechanics, the bra notation is also used for dual vectors.

Linear operator

We define it as a linear map where the domain is the same as the image, i.e. an endofunction.

Examples:

a 2x2 matrix can represent a linear map from $R^{2}$ to $R^{2}$ , so which is a linear operator
the derivative is a linear map from $C^{\infty}$ to $C^{\infty}$ , so which is also a linear operator

Adjoint operator ( $A^{†}$ )

Given a linear operator

A

over a space

S

that has a inner product defined, we define the adjoint operator

A^{†}

(the

†

symbol is called "dagger") as the unique operator that satisfies:

\forall v, w \in S, < A v, w > = < v, A^{†} w >

Self-adjoint operator

Multilinear map

Bilinear map

Linear map of two variables.

More formally, given 3 vector spaces X, Y, Z over a single field, a bilinear map is a function from:

f : X \times Y \to Z

that is linear on the first two arguments from X and Y, i.e.:

f (a_{1} x_{1} + a_{2} x_{2}, y) = a_{1} f (x_{1}, y) + a_{2} f (x_{2}, y)

Note that the definition only makes sense if all three vector spaces are over the same field, because linearity can mix up each of them.

The most important example by far is the dot product from

R^{n} \times R^{n} \to R

, which is more specifically also a symmetric bilinear form.

Bilinear form ( $B (x, y)$ )

Analogous to a linear form, a bilinear form is a Bilinear map where the image is the underlying field of the vector space, e.g.

R^{n} \times R^{m} \to R

Some definitions require both of the input spaces to be the same, e.g.

R^{n} \times R^{n} \to R

, but it doesn't make much different in general.

The most important example of a bilinear form is the dot product. It is only defined if both the input spaces are the same.

Matrix representation of a bilinear form

As usual, it is useful to think about how a bilinear form looks like in terms of vectors and matrices.

Unlike a linear form, which was a vector, because it has two inputs, the bilinear form is represented by a matrix

M

which encodes the value for each possible pair of basis vectors.

In terms of that matrix, the form

B (x, y)

is then given by:

B (x, y) = x^{T} M y

Effect of a change of basis on the matrix of a bilinear form ( $B_{2} = C^{T} B C$ )

C

is the change of basis matrix, then the matrix representation of a bilinear form

M

that looked like:

B (x, y) = x^{T} M y

then the matrix in the new basis is:

C^{T} M C

Sylvester's law of inertia then tells us that the number of positive, negative and 0 eigenvalues of both of those matrices is the same.

Proof: the value of a given bilinear form cannot change due to a change of basis, since the bilinear form is just a function, and does not depend on the choice of basis. The only thing that change is the matrix representation of the form. Therefore, we must have:

x^{T} M y = x_{n e w}^{T} M_{n e w} y_{n e w}

and in the new basis:

x = C x_{n e w} y = C y_{n e w} x_{n e w}^{T} M_{n e w} y_{n e w} = x^{T} M y = (C x_{n e w})^{T} M (C y_{n e w}) = x_{n e w}^{T} (C^{T} M C) y_{n e w}

and so since:

\forall x_{n e w}, y_{n e w} x_{n e w}^{T} M_{n e w} y_{n e w} = x_{n e w}^{T} (C^{T} M C) y_{n e w} ⟹ M_{n e w} = C^{T} M C

(5)

proofwiki.org/wiki/Matrix_of_Bilinear_Form_Under_Change_of_Basis

Multilinear form

See form.

Analogous to a linear form, a multilinear form is a Multilinear map where the image is the underlying field of the vector space, e.g.

R^{n_{1}} \times R^{n_{2}} \times R^{n_{2}} \to R

Symmetric bilinear map

Subcase of symmetric multilinear map:

f (x, y) = f (y, x)

Requires the two inputs

x

and

y

to be in the same vector space of course.

The most important example is the dot product, which is also a positive definite symmetric bilinear form.

Symmetric bilinear form

symmetric bilinear maps that is also a bilinear form.

Matrix representation of a symmetric bilinear form

Like the matrix representation of a bilinear form, it is a matrix, but now the matrix has to be a symmetric matrix.

We can then immediately see that the matrix is symmetric, then so is the form. We have:

B (x, y) = x^{T} M y

But because

B (x, y)

is a scalar, we have:

B (x, y) = B (x, y)^{T}

and:

B (x, y) = B (x, y)^{T} = (x^{T} M y)^{T} = y^{T} M^{T} x = y^{T} M^{T} x = y^{T} M x = B (y, x)

Hermitian form

The complex number analogue of a symmetric bilinear form.

The prototypical example of it is the complex dot product.

Note that this form is neither strictly symmetric, it satisfies:

< x, y > = \overline{< y, x >}

where the over bar indicates the complex conjugate, nor is it linear for complex scalar multiplication on the second argument.

Bibliography:

mathworld.wolfram.com/HermitianForm.html

Matrix representation of a Hermitian form

;

A Hermitian matrix.

Quadratic form

Multivariate polynomial where each term has degree 2, e.g.:

f (x, y) = 2 y^{2} + 10 y x + x^{2}

is a quadratic form because each term has degree 2:

$y^{2}$
$x y$
$x^{2}$

but e.g.:

f (x, y) = 2 y^{2} + 10 y x + x^{3}

is not because the term

x^{3}

has degree 3.

More generally for any number of variables it can be written as:

f (x_{1}, x_{2}, \dots, x_{n}) = \sum_{i, j} a_{i} a_{j} x_{i} x_{j}

There is a 1-to-1 relationship between quadratic forms and symmetric bilinear forms. In matrix representation, this can be written as:

x^{T} B x

where

x

contains each of the variabes of the form, e.g. for 2 variables:

x = [x, y]

(5)

Strictly speaking, the associated bilinear form would not need to be a symmetric bilinear form, at least for the real numbers or complex numbers which are commutative. E.g.:

[x y] [0210] [x y] = [x y] [y 2 x] = x y + 2 y x = 3 x y

(6)

But that same matrix could also be written in symmetric form as:

[0 1.5 1.5 0]

(7)

so why not I guess, its simpler/more restricted.

Positive definite symmetric bilinear form

Symmetric bilinear form that is also positive definite, i.e.:

\forall x, B (x, x) > 0

Matrix representation of a positive definite symmetric bilinear form

A positive definite matrix that is also a symmetric matrix.

Skew-symmetric bilinear map

Subcase of antisymmetric multilinear map:

f (x, y) = - f (y, x)

Skew-symmetric bilinear form

Skew-symmetric bilinear map that is also a bilinear form.

Symmetric multilinear map

Same value if you swap any input arguments.

Antisymmetric multilinear map

Change sign if you swap two input values.

Alternating multilinear map

Implies antisymmetric multilinear map.

Dot product

The definition of the "dot product" of a general space varies quite a lot with different contexts.

Most definitions tend to be bilinear forms.

We use the unqualified generally refers to the dot product of Real coordinate spaces, which is a positive definite symmetric bilinear form. Other important examples include:

the complex dot product, which is not strictly symmetric nor linear, but it is positive definite
Minkowski inner product, sometimes called" "Minkowski dot product is not positive definite

The rest of this section is about the

R^{n}

case.

The positive definite part of the definition likely comes in because we are so familiar with metric spaces, which requires a positive norm in the norm induced by an inner product.

The default Euclidean space definition, we use the matrix representation of a symmetric bilinear form as the identity matrix, e.g. in

R^{3}

M = ⎣ ⎢ ⎡ 100010001 ⎦ ⎥ ⎤

so that:

x \cdot y = [x_{1} x_{2} x_{3}] ⎣ ⎢ ⎡ 100010001 ⎦ ⎥ ⎤ ⎣ ⎢ ⎡ y_{1} y_{2} y_{3} ⎦ ⎥ ⎤ = x_{1} y_{1} + x_{2} y_{2} + x_{3} y_{3}

Orthogonality

Orthonormality

Angle

Cross product ( $x \times y$ )

Jacobi identity

Index picking function

Kronecker delta ( $δ_{i j}$ )

Levi-Civita symbol ( $ε$ )

Denoted by the Greek letter epsilon with \varepsilon encoding in LaTeX.

Definition:

odd permutation: -1
even permutation: 1
not a permutation: 0. This happens iff two more more indices are repeated

Levi-Civita symbol as a tensor

An Introduction to Tensors and Group Theory for Physicists by Nadir Jeevanjee (2011) shows that this is a tensor that represents the volume of a parallelepiped.

It takes as input three vectors, and outputs one real number, the volume. And it is linear on each vector. This perfectly satisfied the definition of a tensor of order (3,0).

Given a basis

(e_{i}, e_{j}, e_{k})

and a function that return the volume of a parallelepiped given by three vectors

V (v_{1}, v_{2}, v_{3})

ε_{i k j} = V (e_{i}, e_{j}, e_{k})

Projection (mathematics)

Matrix

Matrix operation

Determinant ( $d e t$ )

Name origin: likely because it "determines" if a matrix is invertible or not, as a matrix is invertible iff determinant is not zero.

Matrix inverse ( $M^{- 1}$ )

When it exists, which is not for all matrices, only invertible matrix, the inverse is denoted:

M^{- 1}

Invertible matrix

The set of all invertible matrices forms a group: the general linear group with matrix multiplication. Non-invertible matrices don't form a group due to the lack of inverse.

Transpose ( $M^{T}$ )

Transpose of a matrix multiplication

When it distributes it inverts the order of the matrix multiplication:

(M N)^{T} = N^{T} M^{T}

Inverse of the transpose

The transpose and matrix inverse commute:

(M^{T}) - 1 = (M^{- 1})^{T}

Matrix multiplication

Since a matrix

M

can be seen as a linear map

f_{M} (x)

, the product of two matrices

M N

can be seen as the composition of two linear maps:

f_{M} (f_{N} (x))

One cool thing about linear functions is that we can easily pre-calculate this product only once to obtain a new matrix, and so we don't have to do both multiplications separately each time.

System of linear equations

Application of systems of linear equations

No 2x2 examples please. I'm talking about large matrices that would be used in supercomputers.

System of linear equations algorithm

LINPACK benchmarks

Conjugate gradient method

For positive definite matrices only.

TODO application.

TODO speedup over algorithm for general matrices.

www.studentclustercompetition.us/ comments:

The HPCG benchmark uses a preconditioned conjugate gradient (PCG) algorithm to measure the performance of HPC platforms with respect to frequently observed but challenging patterns of computing, communication, and memory access. While HPL provides an optimistic performance target for applications, HPCG can be considered as a lower bound on performance. Many of the top 500 supercomputers also provide their HPCG performance as a reference.

Application of matrix multiplication

math.stackexchange.com/questions/41706/practical-uses-of-matrix-multiplication/4647422#4647422 highlights deep learning applications.

Matrix multiplication algorithm

math.stackexchange.com/questions/30330/fast-algorithm-for-solving-system-of-linear-equations/259372#259372

General Matrix Matrix Multipliation (GEMM)

The terminology GEMM is present on BLAS, and has stuck pretty much.

Matrix decomposition

Eigenvalues and eigenvectors

Applications of eigenvalues and eigenvectors

Characteristic polynomial

Eigenvalue

See: eigenvalues and eigenvectors.

Spectrum (functional analysis)

Set of eigenvalues of a linear operator.

Continuous spectrum (functional analysis)

Unlike the simple case of a matrix, in infinite dimensional vector spaces, the spectrum may be continuous.

The quintessential example of that is the spectrum of the position operator in quantum mechanics, in which any real number is a possible eigenvalue, since the particle may be found in any position. The associated eigenvectors are the corresponding Dirac delta functions.

Eigendecomposition of a matrix

Every invertible matrix

M

can be written as:

M = Q D Q^{- 1}

where:

$D$ is a diagonal matrix containing the eigenvalues of $M$
columns of $Q$ are eigenvectors of $M$

Note therefore that this decomposition is unique up to swapping the order of eigenvectors. We could fix a canonical form by sorting eigenvectors from smallest to largest in the case of a real number.

Intuitively, Note that this is just the change of basis formula, and so:

$Q^{- 1}$ changes basis to align to the eigenvectors
$D$ multiplies eigenvectors simply by eigenvalues
$Q$ changes back to the original basis

Eigendecomposition of a real symmetric matrix

The general result from eigendecomposition of a matrix:

M = Q D Q^{- 1}

becomes:

M = O D O^{T}

where

O

is an orthogonal matrix, and therefore has

O^{- 1} = O^{T}

Sylvester's law of inertia

The main interest of this theorem is in classifying the indefinite orthogonal groups, which in turn is fundamental because the Lorentz group is an indefinite orthogonal groups, see: all indefinite orthogonal groups of matrices of equal metric signature are isomorphic.

It also tells us that a change of basis does not the alter the metric signature of a bilinear form, see matrix congruence can be seen as the change of basis of a bilinear form.

The theorem states that the number of 0, 1 and -1 in the metric signature is the same for two symmetric matrices that are congruent matrices.

For example, consider:

A = [2223]

The eigenvalues of

A

are

1

and

4

, and the associated eigenvectors are:

v_{1} = [- 2, 1]^{T} v_{4} = [2 / 2, 1]^{T}

symPy code:

A = Matrix([[2, sqrt(2)], [sqrt(2), 3]])
A.eigenvects()

and from the eigendecomposition of a real symmetric matrix we know that:

A = P D P^{T} = [- 2 1 2 / 2 1] [1004] [- 2 2 / 2 11]

Now, instead of

P

, we could use

P E

, where

E

is an arbitrary diagonal matrix of type:

[e_{1} 0 0 e_{2}]

With this, would reach a new matrix

B

B = (P E) D (P E)^{T} = P (E D E^{T}) P^{T} = P (E E D) P^{T}

(5)

Therefore, with this congruence, we are able to multiply the eigenvalues of

A

by any positive number

e_{1}^{2}

and

e_{2}^{2}

. Since we are multiplying by two arbitrary positive numbers, we cannot change the signs of the original eigenvalues, and so the metric signature is maintained, but respecting that any value can be reached.

Note that the matrix congruence relation looks a bit like the eigendecomposition of a matrix:

D = S M S^{T}

(6)

but note that

D

does not have to contain eigenvalues, unlike the eigendecomposition of a matrix. This is because here

S

is not fixed to having eigenvectors in its columns.

But because the matrix is symmetric however, we could always choose

S

to actually diagonalize as mentioned at eigendecomposition of a real symmetric matrix. Therefore, the metric signature can be seen directly from eigenvalues.

Also, because

D

is a diagonal matrix, and thus symmetric, it must be that:

S^{T} = S^{- 1}

(7)

What this does represent, is a general change of basis that maintains the matrix a symmetric matrix.

Congruent matrix

Two symmetric matrices

A

and

B

are defined to be congruent if there exists an

S

G L (n)

such that:

A = S B S^{T}

Matrix congruence can be seen as the change of basis of a bilinear form

From effect of a change of basis on the matrix of a bilinear form, remember that a change of basis

C

modifies the matrix representation of a bilinear form as:

C^{T} M C

So, by taking

S = C^{T}

, we understand that two matrices being congruent means that they can both correspond to the same bilinear form in different bases.

Matrix similarity

Metric signature

Metric signature matrix

Eigenvector

See: eigenvalues and eigenvectors.

Eigenvectors and eigenvalues of the identity matrix

math.stackexchange.com/questions/1507290/linear-algebra-identity-matrix-and-its-relation-to-eigenvalues-and-eigenvectors/3934023#3934023

Spectral theorem

Hermitian matrix (complex analogue of symmetric matrix)

Hermitian operator

This is the possibly infinite dimensional version of a Hermitian matrix, since linear operators are the possibly infinite dimensional version of matrices.

There's a catch though: now we don't have explicit matrix indices here however in general, the generalized definition is shown at: en.wikipedia.org/w/index.php?title=Hermitian_adjoint&oldid=1032475701#Definition_for_bounded_operators_between_Hilbert_spaces

Riesz representation theorem

Kronecker product

Named matrix

Dense and sparse matrices