ENTRY LINEAR ALGEBRA Author: Oliver Knill: Spring 2002-Spring 2004 Literature: Standard glossary of multivariable calculus course as taught at the Harvard mathematics department. +------------------------------------------------------------ | adjacency matrix +------------------------------------------------------------ The adjacency matrix of a graph is a matrix A_ij, where A_ij=1 whenever there is an edge from node i to node j in the graph. Otherwise, A_ij=0. Example: the graph with three nodes with the shape of a V has the adjacency matrix A=( 0 1 0 1 0 1 0 1 0 ), where node 2 is conneced to both node 1 and 3 and node 1 and 3 are not connected to each other. +------------------------------------------------------------ | affine transformation +------------------------------------------------------------ An affine transformation is the composition of a linear transformation with a shift like for example: T(x,y) =(2x+y,3x+4 y) + (2,3). +------------------------------------------------------------ | Algebra +------------------------------------------------------------ Algebra was originally the art of solving equations and systems of equations. The word comves from the Arabic "al-jabr" meaning "restauration". The term was used by Mohammed al-Khowarizmi, who worked in Bhagdad. +------------------------------------------------------------ | algebraic multiplicity +------------------------------------------------------------ The algebraic multiplicity of a root y of a polynomial p is the maximal integer k for which p(x)=(x-y)^k q(x). The algebraic multiplicity is bigger or equal than the geometric multiplicity. +------------------------------------------------------------ | angle +------------------------------------------------------------ The angle between two vectors v and w is arccos( (x . y)/(||x|| ||y||), where x dot y is the dot product between x and y and ||x||=sqrtx . x is the length of x. The inverse of cos gives two angles in 0,2 pi. One usually choses the smaller angle. +------------------------------------------------------------ | argument +------------------------------------------------------------ The argument of a complex number z=x+iy is phi if z=r e^i phi. The argument is determined only up to addition of 2 pi. It can be determined as phi = arctan(y/x) + A, where A=0 if x>0 or x=0,y>0 and A=pi if x<0 or x=0 and y<0. For example, arg(i)=pi/2 and arg(-i)=3 pi/2. The argument is the imaginary part of log(z) because log(r e^i phi) = log(r) + i phi. +------------------------------------------------------------ | associative law +------------------------------------------------------------ The associative law is (A B) C = A (B C). It is an identity which some mathematical operations satisfy. For example, the matrix multiplication satisfies the associative law. One says also, that the operation is associative. An example of a product which is not associative is the cross product v x w: if i,j,k are the standard basis vectors, then i x (i x j) = i x k = -j and (i x i) x j = 0 x j = 0. +------------------------------------------------------------ | augmented matrix +------------------------------------------------------------ The augmented matrix of a linear equation Ax=b is the n x (n+1) matrix ( A b ). One considers the augmented matrix when solving a linear system Ax=b. The reduced row echelon form rref ( A b ) contains the solution vector x in the last column, if a solution exists. More generally, a matrix which contains a given matrix as a submatrix is called an augmented matrix. +------------------------------------------------------------ | basis +------------------------------------------------------------ A basis of a linear space is a finite set of vectors v_1, ...,v_n, which are linearly independent and which span the linear space. If the basis contains n vectors, the vector space has dimension n. +------------------------------------------------------------ | basis theorem +------------------------------------------------------------ The basis theorem states that d linearly independent vectors in a vector space of dimension d forms a basis. +------------------------------------------------------------ | block matrix +------------------------------------------------------------ A block matrix is a matrix A, where the only non-zero elements are contained in a sequence of smaller square matrices arranged along the main diagonal of A. Such matrices are also called block diagonal matrices. The matrix A=( 1 2 0 0 0 3 2 0 0 0 0 0 5 0 0 0 0 0 6 7 0 0 0 8 9 ). is an example of a block-diagonal matrix containing a two 2x2, and a 1x1 matrix in its diagonal. +------------------------------------------------------------ | Cauchy-Schwarz inequality +------------------------------------------------------------ The Cauchy-Schwarz inequality tells that |x . y| is smaller or equal to ||x|| ||y||. Equality holds if and only if x and y are parallel vectors. +------------------------------------------------------------ | Cayley-Hamilton theorem +------------------------------------------------------------ The Cayley-Hamilton theorem assures that every square matrix A satisfies p(A)=0, where p(x) = det(A-x) is the characteristic polynomial of A and the right hand side 0 is the zero matrix. +------------------------------------------------------------ | change of basis +------------------------------------------------------------ A change of basis from an old basis v_j to a new basis w_j is described by an invertible matrix S which relates the coordinates (a_1,...,a_n) of a vector a = sum_i a_i v_i in the old v-basis with the coordinates (b_1,...,b_n) of the same vector b=sum_i b_i w_i in the new w-basis. The relation of the coordinates is b = S a In that case, one has v_j = sum_j S^T_ij w_j, where S^T is the transpose of S. For example if v_1 = (1,0), v_2 = (0,1), w_1 = (3,4) w_2 = (2,3), then a=(a_1,a_2)=(5,7) in the v-basis has the coordinates b=(b_1,b_2)=(1,1) in the w-basis. With S = ( 3 2 4 3 ) and S^T=( 3 4 2 3 ) we have b = S a and w_1 = 3 v_1 + 4 v_2, w_2 = 2 v_1 + 3 v_2. +------------------------------------------------------------ | characteristic matrix +------------------------------------------------------------ The characteristic matrix of a square matrix A is the matrix A(x) = (x I-A) , where I is the identity matrix. The characteristic matrix is a function of the free variable x. +------------------------------------------------------------ | characteristic polynomial +------------------------------------------------------------ The characteristic polynomial of a matrix A is the polynomial p(x) = det(x I-A), where I is the identity matrix. It has the form p(x) = x^n - tr(A) x^(n-1) + ... + (-1)^n det(A) where tr(A) is the trace of A and det(A) is the determinant of the matrix A. The eigenvalues of A are the roots of the characteristic polynomial of A. +------------------------------------------------------------ | Cholesky factoriztion +------------------------------------------------------------ The Cholesky factoriztion of a symmetric and positive definite matrix A is A = R^T R, where R is upper triangular with positive diagonal entries. +------------------------------------------------------------ | circulant matrix +------------------------------------------------------------ A circulant matrix is a square matrix, where the entries in each diagonal are constant. If S is the shift matrix which has 1 in the side diagonal and 0 everywhere else like in the 3x3 case: S = ( 0 1 0 0 0 1 1 0 0 ), then a circular matrix can be written as A=a_0 + a_1 S + ... + a_n-1 S^n-1. A general 3x3 circulant matrix has the form A = a + b S + c S^2 which is S = ( a b c c a b b c a ). +------------------------------------------------------------ | classical adjoint +------------------------------------------------------------ The classical adjoint adj(A) of a n x n matrix A is the n x n matrix whose entry a_ij is a_ij = (-1)^(i+j) det(A_ji), where A_ji is a minor of A. The classical adjoint plays a role in Cramer's rule A^(-1) = adj(A)/ det(A). The name "adjoint" comes from the fact that we have a change indices like in the adjoint. However, the classical adjoint has nothing to do with the adjoint. +------------------------------------------------------------ | codomain +------------------------------------------------------------ The codomain of a linear transformation T: X to Y is the target space Y. The name has its origin from naming X the domain of A. +------------------------------------------------------------ | cofactor +------------------------------------------------------------ A cofactor C_ij of a n x n matrix A is the determinant of the (n-1) x (n-1) matrix obtained by removing row i and column j from A and multiplying the result with (-1)^i+j. +------------------------------------------------------------ | coefficient +------------------------------------------------------------ A coefficient of a matrix A is an entry A_ij in the i'th row and the j'th column. For a real matrix, all entries are real numbers, for a complex matrix, the entries can be complex numbers. +------------------------------------------------------------ | column +------------------------------------------------------------ A column of a matrix is one of the vectors ( A_11 A_21 A_31 dots A_m1 ), ( A_1n A_2n A_3n dots A_mn ) of a m x n matrix A. Column vectors are in the image of the transformation x mapsto A(x). +------------------------------------------------------------ | column +------------------------------------------------------------ The matrix A defining a linear equation Ax=b or begineqnarray* A_11 x_1 + dots A_1n x_n = b_1 dots = dots A_m1 x_1 + dots A_mn x_n = b_m endeqnarray* is called the coefficient matrix of the system. The augmented matrix is the m x (n+1) matrix ( A b ), where b forms an additional column. +------------------------------------------------------------ | column picture +------------------------------------------------------------ The column picture of a linear equation Ax = b is that the vector b becomes a linear combination of the columns of A. The linear equation is solvable if the vector b is in the column space of A. +------------------------------------------------------------ | column space +------------------------------------------------------------ The column space of a matrix A is the linear space spanned by the columns of A. +------------------------------------------------------------ | commuting matrices +------------------------------------------------------------ Two commuting matrices A,B satisfy A B = B A. In that case, if A is diagonalizable, then also B is diagonalizable and both A and B share the same n eigenvectors. +------------------------------------------------------------ | commutative law +------------------------------------------------------------ The commutative law A*B = B*A for some operation * is an identity which holds for certain operations like the addition of matrices. Other operations like the multiplication of matrices does not satisfy the commutative law. One says: matrix multiplication is not commutative. +------------------------------------------------------------ | complex conjugate +------------------------------------------------------------ The complex conjugate of a complex number z=x+iy is the complex number x-iy. It has the same length |z| as z. +------------------------------------------------------------ | Complex numbers +------------------------------------------------------------ Complex numbers form an extension of the real numbers. They are obtained by introducing i = (-1)^1/2 and extending the rules of addition (a + ib) + (c + id) = (a + c) + i(b + d) and multiplication (a + ib)(c + id) = (ac - bd) + i(ad + bc). The absolute value r=|x+iy| is the length of the vector (a,b). The argument of z, phi= arg(z) is defined as the angle in 0,2pi) between the x axes and the vector (a,b). Using these polar coordinates one can see the Euler identity z = r exp(i phi) = r cos(phi) + i r sin(phi). +------------------------------------------------------------ | consistent +------------------------------------------------------------ A system of linear equations Ax=b is called consistent, if there exists for every vector b a solution vector x to the equation Ax=b. If the system has no solution, the system is called inconsistent. +------------------------------------------------------------ | continuous dynamical system +------------------------------------------------------------ A continuous dynamical system is defined by an ordinary differential equation d/dt u = f(u) where u=u(t) is a vector valued function and f(u) is a vector field. If f(u) is linear, the equation has the form d/dt u = A u. The name "continuous" comes from the fact that the time variable t is taken in the continuum. This distinguishes the system from discrete dynamical systems u(t+1)=f(u(t)) determined by a map f and where t is an integer. For linear continuous dynamical systems, the origin 0 is invariant. The origin is called asymptotically stable if x(t) to 0 for all initial conditions x(0). For continuous dynamical systems u_t = A u, this is equivalent with the requirement that all eigenvalues of A have a negative real part. In two dimensions, where the trace and the determinant determine the eigenvalues, linear stability is characterized by det(A)>0, tr(A)<0 (stability quadrant). +------------------------------------------------------------ | covariance matrix +------------------------------------------------------------ A covariance matrix A of two finite dimensional random variables x,y with expectation Ex=Ey=0 is defined as A_ij = E x_i y_j , where Ex= (x_1+...+x_n)/n is the mean or expectation of x. The covariance matrix is always symmetric. If the covariance matrix is diagonal, the random variables x,y are called uncorrelated. +------------------------------------------------------------ | Cramer's rule +------------------------------------------------------------ Cramer's rule tells that a solution x of a linear equation Ax=b can be obtained as x_i = det(A_i)/ det(A), where A_i is the matrix obtained by replacing the column i of A with the vector b. +------------------------------------------------------------ | de Moivre formula +------------------------------------------------------------ The de Moivre formula is (cos(x)+i sin(x))^n = cos(nx) + i sin(n x). It is useful to derive trigonometric identities like cos(x)^3-3 sin(x)^2 cos(x)=cos(3x). +------------------------------------------------------------ | determinant +------------------------------------------------------------ The determinant of a n x n square matrix A is the sum over all products A1,pi(1) ... An,pi(n) (-1)^pi, where pi runs over all permutations of 1,2,...,n and (-1)^pi is the sign of the permutation pi. Example: for a 2 x 2 matrix A= ( a b c d ) the determinant is det(A)=ad-bc. Example: For a 3x3 matrix A = ( a b c d e f g h i ), the determinant is det(A)=a e i + b f g + c d h - c e g - b f g - c d h. Properties of the determinant are det(A B)= det(A) det(B), det(A^T)= det(A), det(A^-1)=1/ det(A). +------------------------------------------------------------ | differential equation +------------------------------------------------------------ A differential equation is an equation for a function f in one or several variables which involves derivatives with respect to these variables. An ordinary differential equation is a differential equation, where derivatives appear only with respect to one variable. By adding new variables if necessary (for example for t, or derivatives u_t,u_tt etc, one can write an ordinary differential equation always in the form x_t = f(x). +------------------------------------------------------------ | dilation +------------------------------------------------------------ A dilation is a linear transformation x to b x. Dilations scale each vector v by the factor b but leave the direction of v invariant. +------------------------------------------------------------ | dimension +------------------------------------------------------------ The dimension of a vector space X is the number of basis vectors in a basis of X. +------------------------------------------------------------ | distributive law +------------------------------------------------------------ The distributive law is A*(B+C) = A*B + A*C. The set of matrices with matrix multiplication * and addition + is an example where the distributive law applies. +------------------------------------------------------------ | dot product +------------------------------------------------------------ The dot product v . w of two vectors v and w is the sum of the products v_i w_i of their components v_i, w_i. For complex vectors, the dot product is defined as sum_i overlinev_i w_i. Examples: (3,2,1) . (1,2,-1) = 6. if v . w=0, then the vectors are orthogonal. the length of the vector |v| is the square root of v . v. v . w = |v| |w| cos(alpha), where alpha is the angle between v and w. if A,B are two n x n matrices, then (AB)_ij is the dot product of the i'th row of A with the j'th column of B +------------------------------------------------------------ | echelon matrix +------------------------------------------------------------ The echelon matrix of a matrix A is a matrix rref(A), where the pivot in each row comes after the pivot in the previous row. The pivot is the first nonzero entry in each row. The echelon matrix is also called a matrix in reduced row echelon form. +------------------------------------------------------------ | eigenbasis +------------------------------------------------------------ An eigenbasis to a matrix A is a basis which consists of eigenvectors of A. +------------------------------------------------------------ | eigenvalue +------------------------------------------------------------ An eigenvalue L of a matrix A is a number for which there exists a vector v such that A v= L v. Example: A = ( 3 2 0 4 ) has the eigenvector v = (0,1) with eigenvalue x=4. +------------------------------------------------------------ | eigenvector +------------------------------------------------------------ An eigenvector v of a matrix A is a nonzero vector v for which Av=L v with some number L (called eigenvalue). Example: ( -1 1 1 1 ) has the eigenvector v = (1,1) with eigenvalue L=0. +------------------------------------------------------------ | Elimination +------------------------------------------------------------ Elimination is a process which reduces a matrix A to its echelon matrix rref(A). See row reduced echelon form. +------------------------------------------------------------ | ellipsoid +------------------------------------------------------------ An ellipsoid can be written as the set of points x which satisfy x dot Ax =1, where A is a positive definit matrix. The axes v_i of the ellipse are the eigenvectors of A have the length 1/x_i , where x_i are the eigenvalues of A. +------------------------------------------------------------ | entry +------------------------------------------------------------ An entry or coefficient of a matrix is the number or the variable A(i,j) of a matrix. +------------------------------------------------------------ | expansion factor +------------------------------------------------------------ The expansion factor of a linear map is the absolute value of the determinant of A. It is the volume of the parallelepiped obtained as the image of the unit cube under A. +------------------------------------------------------------ | exponential +------------------------------------------------------------ The exponential exp(A) of a matrix A is defined as the sum exp(A) = 1 + A + A^2/2! + A^3/3! + .... The linear system of differential equations x'=Ax for x(t) has the solution x(t) = exp(A t) x(0). +------------------------------------------------------------ | factorization +------------------------------------------------------------ The factorization of a polynomial p(x) is the representation p(x)= a (L_1-x) ... (L_n-x), where lambda_i are the n roots of the polynomials whose existence is assured by the fundamental theorem of algebra. +------------------------------------------------------------ | Fourier coefficients +------------------------------------------------------------ The Fourier coefficients of a 2pi periodic function f(x) on -pi,pi is c_n = (1/2 pi) int_-pi^pi f(x) exp(-i n x). One has f(x) = sum_n c_n exp(i n x). By writing f(x)=g(x)+h(x), where g(x)=f(x)+f(-x)/2 is even and h(x)=f(x)-f(-x)/2 is odd one can obtain real versions: the even function can be written as a cos-series g(x) = sum_n=0^infinity a_n cos(n x), where a_n=(2/pi) int_0^pi g(x) cos(n x) dx for n>0 and a_0=(1/pi) int_0^pi g(x) dx. The odd function can be written as the sin-series h(x)= sum_n=1^infinity b_n sin(n x), where b_n=(2/pi) int_0^pi h(x) sin(n x) dx. The complex Fourier coefficients c_n are coordinates of f(x) with respect to the orthonormal basis exp(i n x). The real Fourier coefficients are the coordinates of f(x) with respect to orthogonal basis 1, cos(n x), sin(n x), n>0. % The Fourier series of a function f is f(x) = sum_n=-infinity^infinity c_n exp(i n x) or f(x) = sum_n a_n cos(n x) for even functions or f(x)=sum_n=1^infinity b_n sin(n x) for odd functions. +------------------------------------------------------------ | fundamental theorem of algebra +------------------------------------------------------------ The fundamental theorem of algebra states that a polynomial p(x) =x^n+... a_1 x + a_0 of degree n has exactly n roots. +------------------------------------------------------------ | Gauss Jordan elimination +------------------------------------------------------------ The Gauss Jordan elimination is a method for solving linear equations. It was already known by the Chinese 2000 years ago. Gauss called it "eliminatio vulgaris". The method does linear combinations of the rows of a n x (n+1) matrix until the system is solved. Example: 2 x + 4y = 2 3 x + y = 12 x + 2y = 1 3 x + y = 13 x + 2y = 1 - 5y = 10 x + 2y = 1 y = -2 x = 5 y = -2 First, the top equation was scaled, then three times the first equation was subtracted from the second equation. Then the the second equation was scaled. Finally, twice the the second equation was subtracted from the first. +------------------------------------------------------------ | geometric multiplicity +------------------------------------------------------------ The geometric multiplicity of an eigenvalue L is the dimension of ker(L-A). The geometric multiplicity is smaller or equal to the algebraic multiplicity. +------------------------------------------------------------ | Gibbs phenomenon +------------------------------------------------------------ The Gibbs phenomenon describes the error when doing a Fourier approximation of the discontinuous Heavyside function f(x)= -1 if -pi leq x leq 0 1 if 0 < x 0 a_n sin(n x) e^-mu n^2 t, where a_n=(2/pi) int_0^pi f(x) sin(n x) dx are the Fourier coefficients. +------------------------------------------------------------ | Hermitian matrix +------------------------------------------------------------ A Hermitian matrix satisfies A^* = overlineA^T = A, where A^T is the transpose of A and overlineA is the complex conjugate matrix, where all entries are replaced by their complex conjugates. +------------------------------------------------------------ | Hessenberg matrix +------------------------------------------------------------ A Hessenberg matrix A is an upper triangular matrix with only one extra nonzero adjacent diagonal below the diagonal. Example: a general 3 x 3 Hessenberg matrix is A = ( a b c d e f 0 g h ). +------------------------------------------------------------ | Hilbert matrix +------------------------------------------------------------ A Hilbert matrix is a symmetric square matrix, where A_ij = 1/(i+j-1). It is an example of a Hankel matrix and positive definit. Hilbert matrices are examples of matrices which are difficult to invert, because their determinant is small. For example, for n=3, the Hilbert matrix A = ( 1 1/2 1/3 1/2 1/3 1/4 1/3 1/4 1/5 ) has determinant 1/2160. % A hyperplane in n-dimensional space V is a (n-1)-dimensional linear subspace of V. +------------------------------------------------------------ | identity matrix +------------------------------------------------------------ The identity matrix is the matrix I which has 1 in the diagonal and zero everywhere else. The identity matrix I satisfies I A = A for any matrix A. The 3 x 3 identity matrix is A = ( 1 0 0 0 1 0 0 0 1 ). +------------------------------------------------------------ | incidence matrix +------------------------------------------------------------ The incidence matrix of a directed graph with n nodes and m edges is a m x n matrix which has a row for each edge connecting nodes i and j with entries -1 and 1 in columns i, j. Example. The directed graph 1 Rightarrow 2 Leftarrow 3, 1 arrow 4 with 3 edges and 4 nodes has the 3 x 4 incidence matrix A = ( -1 1 0 0 0 1 -1 0 -1 0 0 1 ). +------------------------------------------------------------ | inconsistent +------------------------------------------------------------ A system of linear equations Ax=b is called inconsistent if the system has no solutions. +------------------------------------------------------------ | indefinite matrix +------------------------------------------------------------ An indefinite matrix is a matrix, whith eigenvalues of different sign. A positive definite matrix is an example of a matrix which is not indefinite. +------------------------------------------------------------ | Independent vectors +------------------------------------------------------------ Independent vectors. If no linear combination a_1 v_1 + ... + a_n v_n is zero unless all a_i are zero, then the vectors v_1,...,v_n are called independent. If A is the matrix which contains the vectors v_i as columns, then the kernel of A is trivial. A basis consists of independent vectors. +------------------------------------------------------------ | Independent vectors +------------------------------------------------------------ The linear transformation corresponding to the identity matrix is called the identity transformation. +------------------------------------------------------------ | image +------------------------------------------------------------ The image of a linear transformation T: X to Y, T(x)=Ax is the subset of all vectors y=Ax, x in X in Y. The image is denoted by im(T) or im(A) and is a subset of the codomain Y of T. The image is also called the range. The dimension of the image of T is equal to the rank of A and the dimension satisfies dim( ker(A)) + dim( im(A)) = n, where n is the dimension of the linear space X. +------------------------------------------------------------ | index +------------------------------------------------------------ The index of a linear map T is defined as ind(A) = dim ( ker A) - dim ( coker A), where coker(A) is the orthogonal complement of the image of A. Examples are: The index of a n x n matrix A is dim ( ker A) - dim ( coker A) = 0. The index of the differential operator Df = f' acting on smooth functions on the real line is 1-0 = 1 because D has a one dimensional kernel (the constant functions) and a zero dimensional cokernel (all functions can be obtained as the image of D). The index of D^n is n. The index of the differential operator Df=f' acting on smooth functions on the circle is 1-1=0 because D has a one dimensional kernel (the constant functions) and a one-dimensional cokernel (the constant functions, one can not find a periodic function g such that g'=1). The Atiyah-Singer index theorem relates topological properties of a surface M with the index of a "Dirac operator" T on it. The previous two examples exemply that. T=D is a Dirac operator and the topology of the circle or the line are different. +------------------------------------------------------------ | inverse +------------------------------------------------------------ The inverse of a square matrix A is a matrix B satisfying A B=I and B A=I where I is the identity matrix. For example, the inverse of the transformation A= ( a b c d ) is the transformation B = ( d -b -c a ) / (ad-bc). +------------------------------------------------------------ | invertible +------------------------------------------------------------ A square matrix A is invertible if there exists a matrix B such that A B=I. A matrix A is invertible if and only if the determinant of A is different from zero. +------------------------------------------------------------ | Jordan normal form +------------------------------------------------------------ The Jordan normal form J = S^-1 A S of a square matrix A is a block matrix J = diag(J_1, ..., J_k), where each block is of the form J_k = x_k I_k + N_k, where x_k is an eigenvalue of A, I_k is an identity matrix and N_k is a matrix with 1 in the first sidediagonal. If all eigenvalues of A are different, then the Jordan normal form is a diagonal matrix. +------------------------------------------------------------ | kernel +------------------------------------------------------------ The kernel of a linear transformation T: X to Y, T(x)=Ax is the linear space x in X such that Ax=0 . The kernel is denoted by ker(T) or ker(A) and is a subset of the domain X of T. The dimension of the kernel dim( ker(A)) and the dimension of the image dim( im(A)) are related by dim( ker(A)) + dim( im(A)) = n, where n is the dimension of the linear space X. The kernel of a transformation is computed by building rref(A), the reduced row echelon form of A. Echelon = "series of steps". Every vector in the kernel of rref(A) is also in the kernel of A. +------------------------------------------------------------ | Leontief +------------------------------------------------------------ Wassily Leontief. A Russian-born US economist who was working also at Harvard University. Leontief was a winner of the 1973 Economics Nobel prize for the development of the input-output method and for its application to important economic problems. Linear algebra students find the following problem in textbooks: two industries A and B produce output with value x and y (in millions of dollars). Assume that the consumer demand is a for the product of A and b for the product of B. Assume also an industry demand: p x is transfered from A to B, and q y is transfered from B to A. For which x and y are both the industry and conumer demand satisfied? The problem is equivalent to solving the linear system begineqnarray* x - q y = a -p x + y = b endeqnarray* +------------------------------------------------------------ | Laplace equation +------------------------------------------------------------ The Laplace equation in a region G is the linear partial differential equation u_xx + u_yy = 0. A solution is determined if u(x,y) is prescribed on the boundary of G. On the square 0,pi x 0,pi with boundary conditions 0 except at the side y=pi, where one has u(x,pi)=f(x), one can find a solution via Fourier series: u(x,y) = sum_n>0 a_n sin(n x) sinh(n y)/sinh(n pi), where a_n=(2/pi) int_0^pi f(x) sin(n x) dx. The case with general boundary conditions can be solved by adding corresponding solutions u(x,y),u(y,x),u(x,pi-y),u(pi-y,x) for the other 3 sides of the square. +------------------------------------------------------------ | Laplace expansion +------------------------------------------------------------ The Laplace expansion is a formula for the determinant of A: det(A) = (-1)^i+1 a_i1 det(A_i1)+ ... +(-1)^i+n a_in det(A_in). +------------------------------------------------------------ | leading one +------------------------------------------------------------ A leading one is an entry of a matrix in reduced row echelon form which is contained in a row with this element as the first nonzero entry. +------------------------------------------------------------ | leading variable +------------------------------------------------------------ A leading variable is a variable which corresponds to a leading one in rref(A). +------------------------------------------------------------ | least-squares solution +------------------------------------------------------------ A vector x in R^n is called a least-squares solution of the system Ax=b where A is a m x n matrix, if ||b-Ay|| is less or equal then ||b-Ax|| for all y in R^n. If x is the least-squares solution of Ax=b then Ax is the orthogonal projection of b onto the image im(A). The explicit formula is x = (A^T A)^(-1) A^T b and derived from that A^T (Ax-b) =0 which itself just means that Ax-b is orthogonal to the image of A. +------------------------------------------------------------ | length +------------------------------------------------------------ The length of a vector v is ||v||=(v . v)^1/2 = (v_1^2+ ... + v_n^2)^(1/2). The length of a complex number x+iy is the length of (x,y). The length of a vector depends on the basis, usually it is understood with respect to the standard basis. +------------------------------------------------------------ | linear combination +------------------------------------------------------------ A linear combination of n vectors v_1, ..., v_n is a vector a_1 v_1 + ... + a_n v_n. +------------------------------------------------------------ | Linearly dependent vectors +------------------------------------------------------------ Linearly dependent vectors. If there exist a_1,...,a_n which are not all zero such that a_1 v_1 + ... + a_n v_n =0, then the vectors v_1,...,v_n are called linearly dependent. +------------------------------------------------------------ | Linearity +------------------------------------------------------------ Linearity is a property of maps between linear spaces: it means that lines are maped into lines and the image of the sum of two vectors is the same as sum of the images. For example: T(x,y,z) = (2x+z,y-x) is linear. T(x,y) = (x^2-y,x) is nonlinear. +------------------------------------------------------------ | linear dynamical system +------------------------------------------------------------ A linear dynamical system is defined by a linear map x mapsto Ax. The orbits of the dynamical system are x, Ax, A^2x, ... . +------------------------------------------------------------ | linear space +------------------------------------------------------------ A linear space is the same as a vector space. It is a set which is closed under addition and multiplication with real numbers. +------------------------------------------------------------ | linear combination +------------------------------------------------------------ A sum a_1 v_1 + ... + a_n v_n is called a linear combination of the vectors v_1, ... , v_n. +------------------------------------------------------------ | linear subspace +------------------------------------------------------------ A linear subspace of a vector space V is a subset of V which is also a vector space. In particular, it is closed under addition, scalar multiplication and contains a neutral element. +------------------------------------------------------------ | linear system of equations +------------------------------------------------------------ A linear system of equations is an equation of the form Ax=b, where A is a m x n matrix, x is a n-vector and b is a m-vector. There are three possibilities: consistent with one solution: no row vector (0 ... 0 | 1 ) in rref(A | b). There is exactly one solution if there is a leading one in each column of rref(A). consistent with infinitely many solutions: there are columns with no leading one. Inconsistent with no solutions: there is a row (0 ... 0 | 1 ) in rref(A | b). +------------------------------------------------------------ | logarithm +------------------------------------------------------------ The logarithm log(z) of a complex number z=x+iy neq 0 is defined as log|z|+i arg(z), where arg(z) is the argument of z. The imaginary part of the logarithm is only defined up to a multiple of 2 pi. +------------------------------------------------------------ | Markov matrix +------------------------------------------------------------ A Markov matrix is a square matrix, where all entries are nonnegative and the sum of each column is 1. One of the eigenvalues of a Markov matrix is 1 because A^T has the eigenvector (1,1,...,1). If all entries of a Markov matrix are positive, then A^k v converges to the eigenvector v with eigenvalue 1. This vector is called the "steady state" vector. +------------------------------------------------------------ | matrix +------------------------------------------------------------ A matrix is a rectangular array of numbers. The following 3 x 4 matrix for example consists of three rows and four columns: A = ( 2 8 4 2 1 2 1 3 2 -1 1 2 ). The first index addresses the row, the second the column of the matrix. A n x m matrix maps the m-dimensional space to the n-dimensional space. +------------------------------------------------------------ | Matrix multiplication +------------------------------------------------------------ Matrix multiplication is an operation defined between a (n x m) matrix A and a (m x p) matrix B. (A B)_ij is the dot product between the i'th row of A with the j'th column of B. Example: (n=2, m=3, p=4) ( 2 1 0 1 0 1 ) ( 2 1 0 0 0 0 1 2 1 3 1 1 ) =( 4 2 1 2 3 4 1 1 ). +------------------------------------------------------------ | minor +------------------------------------------------------------ A minor of a matrix A is a matrix A(i,j) which is obtained from A by deleting row i and column j. +------------------------------------------------------------ | nilpotent matrix +------------------------------------------------------------ A nilpotent matrix is a matrix A for which some power A^k is the zero matrix. A nilpotent matrix has only zero eigenvalues. he matrix A = ( 0 1 1 0 0 2 0 0 0 ) for example satisfies A^3=0 and is therefore nilpotent. +------------------------------------------------------------ | non-leading coefficient +------------------------------------------------------------ A non-leading coefficient is an entry in the row reduced echelon form of a matrix A which is nonzero and which comes after the leading 1. The relevance of this definition comes from the fact that the number of columns with non-leading coefficients is the dimension of the kernel of the map. +------------------------------------------------------------ | normal equation +------------------------------------------------------------ The normal equation to the linear equation Ax=b is the consistent system A^T A x = A^T b. +------------------------------------------------------------ | normal matrix +------------------------------------------------------------ A matrix A is called a normal matrix, if A A^T = A^T A. A normal matrix has orthonormal possibly complex eigenvectors. +------------------------------------------------------------ | null space +------------------------------------------------------------ The null space of a matrix A is the same as the kernal of A. It is spanned by the solutions A v = 0. The dimension of the null space is n-r, where n is the number of columns of A and r is the rank of A. +------------------------------------------------------------ | ordinary differential equation +------------------------------------------------------------ An ordinary differential equation is a differential equation, where derivatives appear only with respect to one variable. By adding new variables if necessary (for example for t, or derivatives u_t,u_tt etc. one can write such an equation always in the form x_t = f(x). An ordinary differential equation defines a continuous dynamical system. The initial condition x(0) determines the trajectories x(t). An ordinary differential equation of the form u_t = A u, where A is a matrix is called a linear ordinary differential equation. +------------------------------------------------------------ | orthogonal +------------------------------------------------------------ Two vectors v,w are orthogonal if their dot product v . w vanishes. +------------------------------------------------------------ | orthogonal basis +------------------------------------------------------------ An orthogonal basis is a basis such that all vectors in the basis are orthogonal. +------------------------------------------------------------ | orthonormal basis +------------------------------------------------------------ An orthonormal basis is a basis such that all vectors are orthogonal and normed. +------------------------------------------------------------ | orthonormal complement +------------------------------------------------------------ The orthonormal complement of a linear subspace V in R^n is the set of vectors which are orthogonal to V. +------------------------------------------------------------ | orthogonal projection +------------------------------------------------------------ The orthogonal projection onto a linear space V is proj_V(x) = (x . v_1) v_1 + ... + (x . v_n) v_n, where the v_j form an orthonormal basis in V. Despite the name, an orthogonal projection is not an orthogonal transformation. It has a kernel. In an eigenbasis, a projection has the form (x,y) to (x,0). +------------------------------------------------------------ | Euclidean space +------------------------------------------------------------ Euclidean space is the linear space of all vectors = 1 x n matrices. R^0 is the space 0. The space R^1 is the real linear space of all real numbers, the R^2 is the plane, the R^3 the Euclidean three dimensional space. +------------------------------------------------------------ | parallel +------------------------------------------------------------ Two vectors v and w are called parallel if v both are nonzero and one is a multiple of the other. +------------------------------------------------------------ | parallelepiped +------------------------------------------------------------ A set in R^n is a parallelepiped E if it is the linear image A(Q) of the unit cube Q. The volume of a n-dimensional parallelepiped E in R^n satisfies vol(E)=| det(A)|, in general, vol(E)=( det(A^T A) )^1/2. +------------------------------------------------------------ | partial differential equation +------------------------------------------------------------ A partial differential equation (PDE) is an equation for a multi-variable function which involves partial derivatives. It is called linear if (u+v) and r v are solutions whenever u and v are solutions. Examples of linear PDEs: u_t = c u_x transport equation u_t = b u_xx heat equation u_tt = a u_xx wave equation u_xx + u_yy = 0 Laplace equation u_xx + u_yy = f(x,y) Poisson equation i h u_t = - u_xx + V(x) Schroedinger equation Examples of nonlinear PDE: u_t + u u_x = a u_xx Burger equation u_t + u u_x = - u_xxx Korteweg de Vries equation u_tt-u_xx= sin(x) Sine Gordon equation u_tt-u_xx = f(x) Nonlinear wave equation i h u_t = -u_xx-|x|^2 x Nonlinear Schroedinger equation u_t + u_x(x,t)^2/2 + V(x)=0 Hamilton Jacobi equation +------------------------------------------------------------ | permutation matrix +------------------------------------------------------------ A permutation matrix A is a square matrix with entries A_ij = I_i pi(j) where pi is a permutation of 1,...,n and where I is the identiy matrix. There are n! permutation matrices. Example: for n=3 the permutation pi(1,2,3) = (2,1,3) defines the permutation matrix A = ( 0 1 0 1 0 0 0 0 1 ). +------------------------------------------------------------ | pivot +------------------------------------------------------------ A pivot d is the first nonzero diagonal entry when a row is used in Gaussian elimination. +------------------------------------------------------------ | pivot column +------------------------------------------------------------ A column of a matrix is called a pivot column if the corresponding column of rref(A) contains a leading one. The pivot columns are important because they form a basis for the image of A. +------------------------------------------------------------ | polar decomposition +------------------------------------------------------------ The polar decomposition of a matrix A is A = O B, where O is orthogonal and where B is positive semidefinit. +------------------------------------------------------------ | positive definite matrix +------------------------------------------------------------ A positive definite matrix is a symmetric matrix which satisfies v . A v > 0, for every nonzero vector v. +------------------------------------------------------------ | power +------------------------------------------------------------ The n'th power of a matrix A is defined as A^n=A A^(n-1) = A A .... A. The eigenvalues of A^n are L_i^n, where L_i are the eigenvalues of A. +------------------------------------------------------------ | QR decomposition +------------------------------------------------------------ The QR decomposition of a matrix A is obtained during the Gramm-Schmitt orthogonalization process. It is A=QR, where Q is an orthogonal matrix and where R is an upper triangular matrix. +------------------------------------------------------------ | rank +------------------------------------------------------------ The rank of a linear matrix A is the set of leading 1's in the matrix rref(A). +------------------------------------------------------------ | orientation +------------------------------------------------------------ The orientation of n vectors v_1, ... ,v_n in the n-dimensional Euclidean space is defined as the sign of det(A), where A is the matrix with v_i in the columns. +------------------------------------------------------------ | orthogonal +------------------------------------------------------------ A square matrix A is orthogonal if it preserves length: ||Av|| = ||v|| for all vectors v. +------------------------------------------------------------ | perpendicular +------------------------------------------------------------ Two vectors v and w are called perpendicular if their dot product vanishes: v . w=0. A synonym of perpendicular is orthogonal. +------------------------------------------------------------ | projection matrix +------------------------------------------------------------ A projection matrix is a matrix P which satisfies P^2=P=P^T. It has eigenvalues 1 or 0. The image is a linear subspace S. The vectors in S are eigenvectors to the eigenvalues 1. The vectors in the orthogonal complement of S are eigenvectors to the eigenvalue 0. If A is the matrix which contains the basis of S as the columns, then P = A (A^T A)^-1 A^T is the projection onto S. +------------------------------------------------------------ | pseudoinverse +------------------------------------------------------------ The pseudoinverse of a (m x n) matrix A is the (n x m) matrix A^+ that maps the image of A to the image of A^T. The kernel of A^+ is the kernel of A^T and the rank of A^+ is equal to the rank of A. A^+ A is the projection on the image of A^T and A A^+ is the projection on the image of A. Especially, if A is an invertible (n x n) matrix, then A^+ is the inverse of A. The pseudoinverse is also called Moore-Penrose inverse. +------------------------------------------------------------ | rank +------------------------------------------------------------ The rank of a matrix A is the dimension of the image of A. +------------------------------------------------------------ | Rayleigh quotient +------------------------------------------------------------ The Rayleigh quotient of a symmetric matrix A is defined as the function q(v) = (v . Av)/(v . v). The maximal value of q(v) is the maximal eigenvalue of A and the minimal value of q(v) is the minimal eigenvalue of A. +------------------------------------------------------------ | rotation +------------------------------------------------------------ A rotation is a linear transformation which preserves the angle between two vectors as well as their lengths. A rotation in three dimensional space is determined by the axis of rotation as well as the rotation angle. +------------------------------------------------------------ | rotation matrix +------------------------------------------------------------ A rotation matrix is the matrix belonging to a rotation. A rotation matrix is an example of an orthogonal matrix. Example: In two dimensions, a rotation matrix has the form A = ( cos(t) sin(t) -sin(t) cos(t) ). +------------------------------------------------------------ | rotation-dilation matrix +------------------------------------------------------------ A rotation-dilation matrix is a 2x2 matrix of the form A = ( p -q q p ). It has the eigenvalues p pm i q. The action of A represents the complex multiplication with the complex number p+iq in the complex plane. +------------------------------------------------------------ | row +------------------------------------------------------------ A row of a matrix is formed by horizontal lines A_1j, j=1, .. n of a m x n matrix A. +------------------------------------------------------------ | shear +------------------------------------------------------------ A shear is a linear transformation in the plane which has in a suitable basis the form T(x,y) = (x,y+a x). More generally, in n dimensions, one can define as shear along a m-dimensional plane. If a basis is chosen so that the plane has the from (x,0) then a shear is T(x,y) = (x,y+a x). Shears have determinant 1 and preserve therefore volume. +------------------------------------------------------------ | singular +------------------------------------------------------------ A square matrix A is called singular if it has no inverse. A matrix A is singular if and only if det(A)=0. +------------------------------------------------------------ | singular value decomposition +------------------------------------------------------------ The singular value decomposition (SVD) of a matrix writes a matrix A in the form A = U D V^T, where U,V are orthogonal and D is diagonal. The first r columns of U form an orthonormal basis of the image of A and the first r columns of V form an orthonormal basis of the image of A^T. The last columns of U form an orthonormal basis of the kernel of A^T and the last columns of V form a basis of the kernel of A. +------------------------------------------------------------ | skew symmetric +------------------------------------------------------------ A matrix A is skew symmetric if it is minus its transpose that is if A^T=-A. The eigenvalues of a skew-symmetric matrix are purely imaginary. The eigenvectors are orthogonal. If A is skew symmetric, then B=exp(A t) is an orthogonal matrix, because B^T B = exp(-A t) exp(A t) = 1. For example A = ( 0 1 -1 0 ) gives the rotation matrix exp(A t). +------------------------------------------------------------ | span +------------------------------------------------------------ The span of a set of vectors v_1, ... v_n is the set of all linear combinations of v_1, ... ,v_n. +------------------------------------------------------------ | spectral theorem +------------------------------------------------------------ The spectral theorem tells that a real symmetric matrix A can be diagonalized A = U D U^T, where U is an orthonormal matrix containing an orthonormal eigenbasis in the columns and where D is a diagonal matrix D = diag(x_1,...,x_n), where x_i are the eigenvalues of A. +------------------------------------------------------------ | square matrix +------------------------------------------------------------ A square matrix is a matrix which has the same number of rows than columns. +------------------------------------------------------------ | asymptotically stable +------------------------------------------------------------ A linear dynamical system is called asymptotically stable if A^n x to 0 for all initial values x, where A^n is the n'th power of the matrix A. This is equivalent to the fact that all eigenvalues L of A satisfy |L|<1. +------------------------------------------------------------ | Stability triangle +------------------------------------------------------------ Stability triangle. A discrete dynamical system in the plane is asymptotically stable if and only if the trace and determinant are in the stability triangle | tr(A) |-1 < det(A)<1. A rotation-dilation A is asymptotically stable if and only if det(A)<1. +------------------------------------------------------------ | reduced row echelon form +------------------------------------------------------------ The reduced row echelon form rref(A) of a m x n matrix A is the end product of Gauss-Jordan elimination. The matrix rref(A) has the following properties: if a row has nonzero entries, then the first nonzero entry is 1, called leading 1. if a columns contains a leading 1, then all other entries in that column are 0. if a row contains a leading 1, then every row above contains a leading 1 further left. The algorithm to produce rref(A) from A is obtained by putting the cursor to the upper left corner and repeating the following steps until nothing changes anymore beginenumerate if the cursor entry is zero swap the cursor row with the first row below that has a nonzero entry in that column divide the cursor row by the cursor entry to make the cursor entry = 1 eliminate all other entries in cursor column by subtracting suitable multiples of the cursor row from the other row move the cursor down one row and and to the right one column. If the cursor entry is zero and all entries below are zero, move the cursor to the next column. repeat 4 if as long as necessary and move then to 1 endenumerate +------------------------------------------------------------ | reflection +------------------------------------------------------------ A reflection is a linear transformation T different from the identity transformation which satisfies T^2=1. The eigenvalues of T are -1 or 1. In an eigenbasis, the reflection has the form T(x,y)=(x,-y). The determinant of a reflection is 1 if and only if the dimension of the eigenspace to -1 is even. For example, a reflection at a line in the plane has the matrix A = ( cos(2 x) sin(2 x) sin(2 x) -cos(2 x) ) which has determinant -1. A reflection at the origin in the plane is -I with determinant 1. +------------------------------------------------------------ | root +------------------------------------------------------------ A root of a polynomial p(x) is a complex value z such that p(z)=0. According to the fundamental theorem of algebra, a polynomial of degree n has exactly n roots. +------------------------------------------------------------ | symmetric +------------------------------------------------------------ A matrix A is symmetric if it is equal to its transpose. The spectral theorem for symmetric matrices tells that they have real eigenvalues and symmetric matrices can always be diagonalized with an orthogonal matrix S. +------------------------------------------------------------ | span +------------------------------------------------------------ The span of a finite set of vectors v_1, ... ,v_n is the set of all possible linear combinations c_1 v_1 + c_2 v_2 + ... + c_n v_n where c_i are real numbers. For example, if v_1=(1,0,0) and v_2=(0,1,0), then the span of v_1,v_2 in three dimensional space is the xy-plane. The span is a linear space. +------------------------------------------------------------ | spectral theorem +------------------------------------------------------------ The spectral theorem for a symmetric matrix A assures that A can be diagonalized: there exists an orthogonal matrix S such that A^(-1) A S is diagonal and contains the eigenvalues of A in the diagonal. +------------------------------------------------------------ | standard basis +------------------------------------------------------------ The standard basis of the n-dimensional Euclidean space consists of the columns of the identity matrix I. +------------------------------------------------------------ | symmetric +------------------------------------------------------------ A matrix A is called symmetric if A^T=A. A symmetric matrix has to be a square matrix. Real symmetric matrices can be diagonalized. +------------------------------------------------------------ | Toepitz matrix +------------------------------------------------------------ A Toepitz matrix is a square matrix A, where the entries are constant along the diagonal. In other ways A_ij depends only on j-i. Example: a 3 x 3 Toeplitz matrix is of the form A = ( c d e b c d a b c ). +------------------------------------------------------------ | trace +------------------------------------------------------------ The trace of a matrix A is the sum of the diagonal entries of A. The trace is independent of the basis and is equal to the sum of the eigenvalues of A. +------------------------------------------------------------ | transpose +------------------------------------------------------------ The transpose A^T of a matrix A is the matrix with entries A_ij if A has the entries A_ji. The rank of A^T is equal to the rank of A. For square matrices, the eigenvalues of A^T and A agree because A and A^T have the same eigenvalues. Transposition satisfies (A^T)^T=A, (A B)^T = B^T A^T and (A^(-1))^T = (A^T)^(-1). +------------------------------------------------------------ | triangle inequality +------------------------------------------------------------ The triangle inequality tells that in a linear space, ||v+w|| leq ||v||+||w||. One has equality if and only if the vectors v and w are orthogonal. +------------------------------------------------------------ | eigenvalues of a two times two matrix +------------------------------------------------------------ The eigenvalues of a two times two matrix A = ( a b c d ) are L_1= tr(A)/2 + (( tr(A)/2)^2- det(A))^1/2 and L_2= tr(A)/2 - (( tr(A)/2)^2- det(A))^1/2. The eigenvectors are v_i = ( L_i-d c ) if c neq 0 or v_i = ( b L_i-a ) if b neq 0. (If b=0,c=0, then the standard vectors are eigenvector.) +------------------------------------------------------------ | unit vector +------------------------------------------------------------ A unit vector is a vector of length 1. A given nonzero vector can be made a unit vector by scaling: v/||v|| is a unit vector. +------------------------------------------------------------ | Vandermonde Matrix +------------------------------------------------------------ A Vandermonde Matrix is a square matrix with entries A_ij = x_i^j-1, where x_1,...,x_n are some real numbers. The determinant of a Vandermonde Matrix is prod_j>i (x_j-x_i). Example: x_1=2,x_2=3,x_3=-1 defines the Vandermonde Matrix A = ( 1 2 4 1 3 9 1 -1 1 ) which has the determinant det(A) = (3-2) (-1-2) (-1-3) = 12. +------------------------------------------------------------ | vector +------------------------------------------------------------ A vector is a matrix with one column. The entries of the vector are called coefficients. +------------------------------------------------------------ | vector space +------------------------------------------------------------ A vector space X is a set equipped with addition and scalar multiplication. A vector space is also called a linear space. The addition operation is a group: f+g = g+f Commutativity (f+g)+h = f+(g+h) Associativity f+0 = 0 Existence of a neutral element f+x = 0 Existence of a unique inverse The scalar multiplication satisfies: r (f+g) = r f + r g Distributivity (r+s) f = r f + s f Distributivity r (s f) = (r s) f Associativity 1 f = f One element +------------------------------------------------------------ | wave equation +------------------------------------------------------------ The wave equation is the linear partial differential equation u_tt = c^2 u_xx where c is a constant. The wave equation on a finite interval 00 a_n sin(n x) cos(n c t) + b_n sin(n x) sin(n c t) where a_n=(2/pi) int_0^pi f(x) sin(n x) dx, and b_n=(2/pi) int_0^pi g(x) sin(n x) dx/(c n) are Fourier coefficients. +------------------------------------------------------------ | zero matrix +------------------------------------------------------------ This file is part of the Sofia project sponsored by the Provost's fund for teaching and learning at Harvard university. There are 157 entries in this file. COUNT: 157