Matrix Reference Manual: Algebraic Structures (original) (raw)

Go to: Introduction, Notation, Index

Abelian Group

See under Commutative Group.

Basis

A set of vectors u, v, ..., z form a basis for asubspace S iff they span S and arelinearly independent.

• All bases for a subspace S contain the same number of vectors. This number is the dimension of S.

Characteristic of an Integral domain or Field

All integral domains (and hence fields) contain at least two elements: 0 and 1. The_characteristic_ of an integral domain is the minimum number of 1's that must be added together to equal 0. The characteristic equals zero if no sum of 1's ever equals 0.

• The characteristic of an integral domain or field is always either 0 or a prime number.
• A field with characteristic 0 is infinite but not all infinite fields have 0 characteristic.
• The integers, rationals, reals and complex numbers all have characteristic 0.
• If an integral domain has characteristic p!=0, then (x+y)p = xp +yp for all x, y.
• If x is a member of a field with characteristic 2, then x = -x. For all other fields x = -x implies x = 0.

Commutative or Abelian Group

A group having the operation + is commutative orAbelian if a+b=b+a for all a and b in G.

Dimension

The dimension of a subspace S, dim(S), is the number of vectors in a basis for S.

• dim(S) equals the maximum number of vectors in a linearly independent set taken from S.
• dim(S) equals the minimum number of vectors in a set that spans S.

Equivalence Relation

An equivalence relation is a relation that divides the set into disjoint classes and that satisfies the three axioms given below. We write x ~y if x and y are in the same class, i.e. if the relation is true for the pair x and y. Axioms:

1. Reflexive: x ~ x for all x
2. Symmetric: x ~ y iff y ~ x
3. Transitive: If x ~ y and y ~ z thenx ~ z

Field

A field F (also called a rational domain) is an integral domain in which every non-zero element has a multiplicative inverse.

• The non-zero elements of F form a commutative group.
• If x is a member of a field with characteristic 2, then x = -x. For all other fields x = -x implies x = 0.
• The rationals, reals and complex numbers are all fields.

Galois Field

A field with a finite number of elements, k, is a _Galois Field_and denoted by GF(k).

• The number of elements in a Galois field is always of the form_pn_ where p is a prime and n a positive integer.
• To within an isomporhpism, there is precisely one Galois field of order_pn_.
• The characteristic of GF(pn) equals p.
• For prime p, GP(p) is obtained by using the normal rules of arithmetic on the integers modulo p.

Group

A group G is a set of elements a, b, c, ... with a binary operation + satisfying:

1. Closure: a+b is in G for all a and b in G
2. Associativity: a+(b+c) = (a+b)+c for all a, b, c in G(thus a+b+c is unambiguous)
3. Identity: There exisits an identity element, e, in G such that e+a=a for all a in G
4. Inverse: For each a in G, there exists an element b in_G_ satisfying a+b=e.

Inner Product

An inner product is a scalar function defined on ordered pairs <x, y> of vectors that satisfies:

1. Positive: If x=0, then <**x**,**x**> =0 else <**x**, **x**> > 0
2. Additive: <**x**+**y**, **z**> = <**x**,**z**> + <**y**, **z**>
3. Homogeneous: ,cx, y> = c<**x**, **y**> for all scalars c
4. Hermitian: <**x**, **y**> = conj(<**y**,**x**>)

where "scalar" refers to the field associated with the vector space. Note that condition 4 implies that <**x**, **x**> is real.

• Every inner product defines a vector norm as ||x|| = sqrt (<**x**, **x**>)
  • A vector norm may be derived from an inner product iff it satisfies the parallelogram identity: ||x+y||2+||x-y||2=2||x||2+2||y||2
  • If ||x|| is derived from <x**, y> then 4Re(<**x**, **y**>) = ||x+y||2-||x-y**||2 = 2||x+y||2-||x||2-||y||2
• The euclidean inner product is <**x**, **y**> =yHx
  • The euclidean norm is ||x|| = sqrt (xHx)

Integral Domain

An integral domain, D, is a ring of elements a, b, c, ... in which:

1. Identity: There is an identity element, 1, such that 1*a = a for all a in D.
2. Commutativity: a*b = b*a for all a and b in D
3. Cancellation: If a != 0, then a*b = a*c implies b = c.

Linear Independence

A set of vectors u, v, ..., z are linearly independent iff au+bv+,,,+fz = 0 implies that_a_= _b_= ...= f =0.

Norm

A norm is is a real-valued function f(x) defined on a ring of objects satisfying the following:

• f(0) = 0
• f(x) > 0 for all x != 0
• f(cx) = |c| f(x)
• Triangle Inequality: f(x+y) <= f(x) + f(y)

Note that a matrix norm has to satisfy the additional condition ||XY|| <= ||X|| ||Y||

Projective Space

The projective space, P(V), of a vector space, V, consists of the set of all one-dimensional subspaces of V.
Alternatively, if we define an equivalence relation on the non-zero elements of V with x ~ y iff x = cy for some non-zero scalar c, then the equivalence classes are the elements of P(V).

• We define RP_n_ = P(R_n_+1) and CP_n_ = P(C_n_+1)
• If V has dimension n+1, P(V) has dimension n. P(V) is not itself a vector space but it can be viewed as the union of (i) a vector space of dimension n and (ii) a set of "ideal points" of dimension _n_-1 [see 3 below].
• The elements of P(V) are the homogeneous vectors of V.
• The elements of RP_n_ can be visualized in several ways:
  1. Rays: Lines through the origin in R_n_+1. These are precisely the one-dimensional subspaces of R_n_+1.
  2. Hypersphere: Pairs of antipodal points on the unit sphere in R_n_+1. These are obtained by taking the equivalence class elements having unit length.
  3. Augmented Affine Plane: The union of (i) Points in the affine subspace that is defined by xn+1=1 and that is isomporphic to R_n_ and (ii) a set of "ideal points" (or "points at infinity") isomorphic to RP_n_+1 having that_xn_+1=0. Each of the ideal points corresponds to a "direction" in the subspace.
     • For n=1, we have the union of (i) a line isomrphic to R1 and (ii) a single point at infinity.
     • For n=2, we have the union of (i) a plane isomorphic to R2 and (ii) a circle at infinity in which opposite points are identified..

Ring

A ring R is a set of elements a, b, c, ... with two binary operations + and * such that:

1. R is a commutative group with respect to + in which the identity element is written 0 and the inverse of the element a is written -a.
2. Closure: a*b is in R for all a and b in R
3. Associativity: a*(b*c) = (a*b)*c for all a, b, c in R(thus a*b*c is unambiguous)
4. * is Distributive over +: a*(b+c) = (a*b) + (a*c) and (a+b)*c = (a*c) + (b*c)

Span

A set of vectors u, v, ..., z span a subspace S iff all members of S can be expressed in the form_a_u+bv+,,,+fz where a,b, ..., f are scalars.

Subspace

A subspace S of a vector space, V, over a field F is a subset of the vectors in V that satisfies the following closure property: if x and yare elements of S then so is ax+by for any_a_ and b in F.

• The largest subspace is the entire vector space V.
• The smallest subspace consists of the single vector 0.

Vector Space

A vector space, V, over a field F is a set of elements (called vectors)x, y, z, ... that form a commutative group under an operation + such that for any x, y in V and a, b in F:

1. Closure: ax is an element of V
2. Distributivity: a(x+y) = ax +ay
3. Distributivity: (a+b)x = ax +bx
4. Associativity: (ab)x =a(bx)
5. Identity: 1x = x where 1 is the multiplicative identity in the field

Note that the symbol + is used both for the addition of vectors and for elements of the field and that the symbol * is used both for the product of a field element (scalar) and a vector as well as the product of two scalars. In practice this causes no confusion.

This page is part of The Matrix Reference Manual. Copyright © 1998-2022 Mike Brookes, Imperial College, London, UK. See the file <gfl.html> for copying instructions. Please send any comments or suggestions to "mike.brookes" at "imperial.ac.uk".
Updated: Id:vector.html112912021−01−0518:26:10ZdmbId: vector.html 11291 2021-01-05 18:26:10Z dmb Id:vector.html112912021−01−0518:26:10Zdmb