finals: sections 1.1 - graph and adjacency matrices Flashcards
what is a linear equation?
a1x1 + a2x2 + … + anxn = b
where
a1, a2, …, an are real or complex numbers
b is a real or complex number
x1, x2, …, xn are variables
when are two linear systems equivalent?
if they have the same solution set
what is a solution set of a linear system?
the set of all solutions that makes all of the linear equations in the system true
a system of linear equations has : (solutions)
- exactly one solution
- infinitely many solutions
- no solution
when is a system of linear equations consistent?
when the system has at least one solution
when is a system of linear equations inconsistent?
when the system has no solution
what is a coefficient matrix?
the coefficients attached to the variables are put into a matrix
what is an augmented matrix?
a coefficient matrix with an added column of constants (that are the entries in the b vector)
what is the size of a matrix?
of rows x # of columns (rows x cols)
what are the three elementary row operations?
- Replacement: replace one row by the sum of itself and a multiple of another row
- Interchange: interchange two rows
- Scaling: multiply all entries in a row by a nonzero constant
when are two matrices row equivalent?
two matrices are row equivalent if there a exists a sequence of elementary row operations that transforms one matrix into another
if the augmented matrices of two linear systems are row equivalent __________________
then the two systems have the same solution set
what are the two fundamental questions about a linear system?
1) is the system consistent? that is, does it have at least one solution?
2) if a solution exists, is it the only one?
what is the leading entry of a row mean?
the leftmost nonzero entry in a nonzero row
what are the conditions for a matrix to be in echelon form?
1) all nonzero rows are above any rows of zeros
2) each leading entry of a row is a column to the right of the leading entry of the row above it (lower triangle of zeros)
3) all entries in the column below a leading entry are zeros (lower triangle of zeros)
what are the conditions for a matrix to be in reduced row echelon form?
it must satisfy the conditions to be in echelon form and these two conditions:
1) the leading entry in each nonzero row is 1
2) each leading 1 is the only nonzero entry in its column
is the reduced row echelon form (RREF) of a matrix unique?
yes
is the echelon form of a matrix unique?
no
what is a pivot position in a matrix?
it is a location in a matrix A that corresponds to a leading 1 in the RREF of A.
what is a pivot column?
a column of A that contains a pivot position
what is span? (use span{v1, …, vp})
span{v1, …, vp} is the set of all the linear combinations of v1, …, vp
what is a vector equation?
x1[vector] + x2[vector] + … + xp[vector] = [b vector]
asking if a vector b is in span{v1, …, vp} is the same as asking _______________
does the augmented matrix [v1 … vp b] have a solution?
the zero vector is ALWAYS in ________
span
the equation Ax = b has a solution if and only if __________
b is a linear combination of the columns of A
what is the definition of a graph G? (graphs and adjacency matrices)
a mathematical structure used to model pairwise relations between objects. a graph is defined as a pair G = (V, E)
in a graph G = (V, E), what is V?
a set of vertices (or nodes)
in a graph G = (V, E), what is E?
a set of edges, or links, which are two element subsets of fV
what is an undirected graph?
edges have no direction
what is a directed graph?
edges have a direction
what is a weighted graph?
each edge has an associated weight
what is an unweighted graph?
edges do not have weights
what is the definition of an adjacency matrix?
it is a square matrix used to represent a graph G. the elements of A are used to indicate whether pairs of vertices are adjacent (connected to each other) or not in the graph
what does a 1 mean in an adjacency matrix?
the two nodes are connected to each other
what does a 0 mean in an adjacency matrix?
the two nodes are NOT connected to each other
