Algebraic Structures

Go to: Introduction, Notation, Index

Abelian Group

Basis

A set of vectors u, v, ..., z form a basis for a subspace S iff they span S and are linearly 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 = x^p + y^p 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 or Abelian 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 then x ~ 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 pⁿ where p is a prime and n a positive integer.
• To within an isomporhpism, there is precisely one Galois field of order pⁿ.
• The characteristic of GF(pⁿ) 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||²+||x-y||²=2||x||²+2||y||²
  • If ||x|| is derived from <x, y> then 4Re(<x, y>) = ||x+y||²-||x-y||² = 2||x+y||²-||x||²-||y||²
• The euclidean inner product is <x, y> = y^Hx
  • The euclidean norm is ||x|| = sqrt (x^Hx)

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

• 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ⁿ = P(Rⁿ⁺¹) and CPⁿ = P(Cⁿ⁺¹)
• 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ⁿ can be visualized in several ways:
  1. Rays: Lines through the origin in Rⁿ⁺¹. These are precisely the one-dimensional subspaces of Rⁿ⁺¹.
  2. Hypersphere: Pairs of antipodal points on the unit sphere in Rⁿ⁺¹. 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 x_n+1=1 and that is isomporphic to Rⁿ and (ii)  a set of "ideal points" (or "points at infinity") isomorphic to RPⁿ⁺¹ having that x_n+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 R¹ and (ii) a single point at infinity.
     • For n=2, we have the union of (i) a plane isomorphic to R² 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 au+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 y are 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.