-
Notifications
You must be signed in to change notification settings - Fork 0
Melvin Low edited this page Jun 11, 2017
·
3 revisions
Let dim U = n, dim W = m, T element of L(U, W).
T can be defined by transformations of basis vectors {u_1...u_n} of U into vectors in W. As such,
(Tu_1 = a_1*w_1 + ... + a_m*w_m) for all basis vectors u defines a linear transformation.
Null space = all vectors u s.t. Tu = 0
Range = all vectors w s.t. there exists some u where Tu = w
T maps subspaces to subspaces, and the inverse is true as well. Hence Range T is
a subspace of W and null T is a subspace of U
Fundamental theorem (rank-nullity): dim U = dim Null T + dim Range T
Implications:
1) if n > m, Tx = 0 must have a solution (dim null T > 0)
2) if n < m, Tx = c may not have a solution for some c (dim range T < dim w)
T is injective or one-to-one if Tu = Tv implies u = v. Injective implies null space is {0}.
T is surjective or onto if Range T = W.
T is invertible if it is injective and surjective (bijective). An isomorphism between U and W
exists if there is an invertible linear map between the two.
S is the inverse of T if ST is identity on U and TS is identity on W.
If T' element of L(V, V), then injective/surjective/bijective/invertible each imply the others,
because of rank-nullity theorem.
Cool:
If T is injective, it has a left inverse (ST is identity on U). Hence T has a left inverse when null T = 0,
or in other words dim U = dim range T <= dim W. (dim U <= dim W; corresponding matrix *cannot* be fat)
If T is surjective, it has a right inverse (TS is identity on W). Hence T has a right inverse when
dim U = dim null T + dim range T >= dim range T = dim W (dim U >= dim W; corresponding matrix
*cannot* be skinny)
These two show again that T is invertible iff it is injective and bijective, which
means that dim U = dim W (the corresponding matrix, see below, must be square).
M(T, u_1...u_n, w_1...w_m) is a matrix for T for the given basis vectors.
M is defined as follows:
Let Tu_i = sum c_ji * w_ji, as mentioned in the previous section. This defines
each basis vector of U in terms of a vector in W. The corresponding matrix for T
is [c_*1 ... c_*n], where c_*i denotes the column vector [c_1i ... c_mi]'
Similarly, a vector u in U can be represented by the nx1 column vector consisting
of the n coefficients of the linear combination of the n basis vectors of u.
FROM the above definitions can be derived the definition of matrix addition, scalar multiplication, and matrix multiplication! (Matrix multiplication corresponds to linear transformation
composition. Note: If L and S are both linear, LS is linear)
When multiplying Mv, the result is a linear combination of the columns of M. The possible
outputs, then, or 'range', is spanned by the columns of M. *Rank* is the dimension of this
columnspace. Column rank = row rank (proof on wikipedia).
Rank corresponds to dim Range T. hence m - rank = dim null T (rank nullity theorem).
If a matrix has rank = n, then it is injective because n - (dim range T = n) = 0 = dim null T. Hence
it has a left inverse.
If a matrix has rank = m, it is surjective, because rank = m = dimW. Thus,
it has a right inverse.
If a matrix has rank = m = n, it has full rank and has the following properties:
1) is square, because m = n
2) surjective (see above)
3) injective (see above)
4) invertible
1) Fundamental Theorem of Algebra: All complex polynomials have a root. In particular, this means that a complex polynomial p(z) of degree m can be decomposed as follows:
p(z) = c(z - r_0)(z - r_1)...(z - r_m), where the r's are the roots. (get this by recursively factoring out the root and then reapplying the theorem)
2) Let z and a be complex numbers. Let * be the complex conjugate. Then (az)* = a*z* and (a + z)* = a* + z*
3) Then if r is a root of a polynomial with <<real>> coefficients a, r* is also a root. To see this:
if a_0r + a_1r^2 + ...a_mr^m = 0, then:
(a_0r + a_1r^2 + ...a_mr^m)* = 0* = 0
a_0r* + a_1(r*)^2 + ...a_m(r*)^m = 0
Hence r* is a root if r is a root.
4) A real polynomial p(z) can be factored into linear and quadratic terms:
p(z) = c(z - r_0)(z - r_1)*...*(az^2 + bz + c)*...
This follows from 1) (handwavy argument here, muliplicity issues need more nitpicking):
Any real roots are preserved (linear factors), and the complex roots exist in
pairs (from #3) so they are muliplied together to get the quadratic terms.
This will be a listing of some key results and definitions. The proofs are complicated.
An operator is a linear map that maps a vector space into itself. In other words, T is
an element of L(V). This is important primarily because operators can be exponentiated.
It is not true that a subspace of V will be mapped to itself under an operator T of V.
For example, let V = U1 <direct sum> U2. T may map U1 to U2 and vice versa.
We say that a subspace is <invariant> under T if T maps the subspace to itself. This
is, again, important because because we can exponentiate T and apply it to the subspace.
Clearly V is invariant under T, and null T is invariant under T (because 0 is in null T).
Lets look at one dimensional subspace. Given a vector v in V, we can define the subspace as:
S = { au | a in F }.
This subspace is invariant under T if T(u) = b*u, because then T(a*u) = a*b*u. We say that b
is an eigenvalue of T with eigenvector u. In other words, an eigenvalue of T
corresponds with a one dimensional subspace of V invariant under T.
If there exists a nonzero vector u such that Tu = bu for some b in F, then we say that
b is an eigenvalue with eigenvector v. Note that:
Tu - bu = 0
(T - bI)u = 0
This shows that the set of eigenvectors for a particular eigenvalue is the nullspace
of (T-bI) and thus a subspace of V.
Eigenvectors corresponding to different eigenvalues are linearly independent. This means
that a vector space of dimension N can have at most N eigenvalues.
Trick: If a vector v can be written as a linear combination of eigenvectors [a1*w1+...+an*wn] of T,
Then Tv = T(a1*w1...an*wn) = a1*u1*w1 + ... + an*un*wn where the u's are the corresponding eigenvalues.
Then T^n(v) = a1 * u1^n * w1 + ... + an * un^n * wn. This can be used to compute the fibonacci sequence
is near constant time.
Cool: If two graphs G_1 and G_2 are isomorphic, then their adjacency matrices are related via
the formula P*A_1*P^(-1) = A_2, where P is a permutation matrix with one 1 in every column and row (to see
why, examine how matrices are defined in the section below. If the nodes of the graph n_1 ... n_n are
basis vectors, then a permuation matrix P is simply mapping each node to another node). From this definition,
it is easy to derive that the adjacency matrices will share the same eigenvalues.
- Every operator on a finite-dimensional, nonzero complex vector space has an eigenvalue.
- Every operator on a complex vector space V has an upper-triangular matrix with respect to some basis of V.
- If T has an upper-triangular matrix with respect to some basis of V, then T is invertible if and only if
all the entries on the diagonal of the matrix are nonzero.
- The entries on the diagonal are the eigenvalues of T, since T - lambda I will have a zero on the diagonal
and thus be not invertible (not injective, hence an eigenvector exists).
Diagonal matrices:
- An operator has a diagonal matrix iff it has dim V distinct eigenvalues.
- Every operator on a finite-dimensional, nonzero real vector space has an invariant subspace of dimension 1 or 2.
- Every operator on an odd-dimensional real vector space has an eigenvalue.
Putting everything together,
1) a square matrix (real or complex entries) should always have an eigenvalue, but it may not be real.
2) a square matrix of odd dimension consisting of real entries always has a real eigenvalue.
3) in a square matrix of real coefficients, the complex eigenvalues always come in conjugate pairs