Algebra I and II for Section IIIB (Electrical Engineering), 1998/99

Topics of the course:

• Systems of linear equations, Gaussian elimination
  • Examples
  • Derivation of the algorithm
  • Elimination and back-substitution
  • Consistency conditions
  • Consequences of the final elimination scheme
  • Computational costs
• Matrices
  • Definition and special matrices
  • Calculating with matrices
  • Transpose of a matrix
  • The inverse of a quadratic matrix
  • Gauss-Jordan algorithm
  • Orthogonal matrices, Givens' rotations
  • Elementary matrices for Gaussian elimination
  • LR factorization
  • Roundoff errors
  • Pivot strategies
• Determinants
  • Definition and geometric interpretation
  • Basic properties
  • Efficient calculation of determinants
  • Determinants and systems of linear equations
• Vector spaces
  • Definition and examples
  • Spaces of polynomials and continuous functions
  • Some consequences of the vector space axioms
  • Linear subspaces
  • Linear independence, basis and dimension
  • Coordinates
  • Normed vector spaces
  • Hölder's inequality
  • Minkowski's inequality
  • The scalar product for real and complex vector spaces
  • The Schwarz inequality
  • Gram-Schmidt orthogonalization
• Method of least squares
  • Normal equations
  • QR factorization
• Linear maps
  • Linear maps and matrices
  • Linear maps and the scalar product
  • Endomorphisms of vector spaces
  • Coordinate transformations
  • Norm of a matrix
  • Characterisation of orthogonal maps
• The eigenvalue problem
  • Eigenvalues and characteristic polynomials
  • Eigenvectors
  • Algebraic and geometric multiplicity
  • Eigenvalue problem for symmetric matrices
  • Powers of symmetric matrices
  • 2-norm of a matrix
  • Condition numbers
• Applications of the eigenvalue problem
  • Coupled systems of linear differential equations with constant coefficients
  • First and second order systems
  • Turning a higher order differential equation into a first order system
  • Curves and surfaces of second order
• Numerics of the eigenvalue problem
  • Forward and backward vector iteration
  • Jacobi rotations
  • Jacobi's method for symmetric matrices

• Propositional and first order predicate logic
  • Truth tables
  • Connectives (and, or, negation, implication, equivalence)
  • Associativity and commutativity
  • Double negation law
  • De Morgans's laws
  • Distributivity
  • Existential and universal quantifier
  • Negation laws
• Set theory
  • Cantor's definition of a set
  • Antinomies
  • Zermelo-Fraenkel axioms
  • Operations on sets
  • Relations
  • Functions (Biggs, 2.1)
  • Surjections, injections, bijections (Biggs, 2.2)
  • Finite and infinite sets (Biggs, 2.5)
  • Example: infinitely many primes (Biggs, 2.5)
  • Cardinality
  • Power set has a larger cardinality
• Combinatorics
  • Addition principle (Biggs, 3.1)
  • Counting sets of pairs and tuples (Biggs, 3.2)
  • Functions, words and selections (Biggs, 3.4)
  • Injections as ordered selections without repetition (Biggs, 3.5)
  • Binomial numbers (Biggs, 4.1)
  • Unordered selections with repetition (Biggs, 4.2)
  • The binomial theorem (Biggs, 4.3)
  • The sieve principle (Biggs, 4.4)
  • Partitions of a set (Biggs, 5.1)
  • Classification and equivalence relations (Biggs, 5.2)
  • Distributions and multinomial numbers (Biggs, 5.3)
• Graph theory
  • Graphs and their representation (Biggs, 8.1)
  • Isomorphism of graphs (Biggs, 8.2)
  • Valency (Biggs, 8.3)
  • Complete graphs, cyclic graphs, Petersen graph, hypercubes
  • Paths and cycles (Biggs, 8.4)
  • Trees (Biggs, 8.5)
  • Colouring the vertices of a graph (Biggs, 8.6)
  • The greedy algorithm for vertex-colouring (Biggs, 8.7)
  • Characterisation of bipartite graphs (Biggs, 8.7)
  • Digraphs and tournaments (Biggs, 11.1)
  • Networks and critical paths (Biggs, 11.2)
  • Flows and cuts (Biggs, 11.3)
  • The max-flow min-cut theorem (Biggs, 11.4)
  • Breadth-first search (Biggs, 9.5)
  • The labelling algorithm for network flows (Biggs 11.5)
• Modular arithmetic
  • Congruences (Biggs, 6.1)
  • Z_m and its arithmetic (Biggs, 6.2)
  • Invertible elements of Z_m (Biggs, 6.3)
  • Euler's function (Biggs, 3.3)
  • Theorems of Euler and Fermat (Biggs, 6.3)
• Algebraic structures
  • The axioms of a group (Biggs 13.1)
  • Examples of groups (Biggs 13.2)
  • Homomorphisms and isomorphisms of groups (Biggs, 13.5)
  • Rings (Biggs, 15.1)
  • Invertible elements of a ring (Biggs, 15.2)
  • Fields (Biggs, 15.3)
  • Polynomials (Biggs, 15.4)
  • Ideals in Rings (Biggs, 17.5)
• Error-correcting codes
  • Words, codes, errors, Hamming distance, decoding (Biggs, 17.1)
  • Linear codes (Biggs, 17.2)
  • Construction of linear codes (Biggs, 17.3)
  • Correcting errors in linear codes (Biggs, 17.4)
  • Perfect codes, Hamming codes (Biggs, 17.4)
  • Cyclic codes (Biggs, 17.5)

1. Kaspar Nipp and Daniel Stoffer, Lineare Algebra, Eine Einführung für Ingenieure unter besonderer Berücksichtigung numerischer Aspekte, 3. Auflage, vdf Hochschulverlag AG an der ETH Zürich, 1994.
2. Norman L. Biggs: Discrete Mathematics, revised edition, Oxford University Press, 1989.

Please send comments and suggestions to Uwe Schmock, email: schmock@fam.tuwien.ac.at. Last update: June 14, 2003