Cryptography Reference
In-Depth Information
where
c
j
v
j
=(
c
j
v
1
,j
,c
j
v
2
,j
,...,c
j
v
n,j
), and
0=(0
,
0
,...,
0) is the
zero vector
of length
n
. Since
i
=
j
c
j
v
j
, the relation given in (A.4) where
not all coe
7
cients
are 0, is a
linear dependency relation
(see Definition A.39 on page 490). Gaussian
elimination uses the basic notions of linear algebra to define matrices with the
vectors
v
j
as columns, then performs elementary row operations to put them
into a form to determine the dependency relations therefrom, if there are any.
The basic point from elementary linear algebra is that
if the number of vectors
is greater than the dimension of the vector space over the field, then there must
be a dependency relation
. For instance, if
m>n
in (A.4), then at least one of
the
c
j
=0.
In the above, we mentioned the notion of elementary row operations. They
are defined as follows.
Elementary Row Operations
1. Interchange two rows of the matrix.
2. Multiply all elements of a row of the matrix by a nonzero scalar.
3. Add to any row of the matrix any other row of it multiplied by a nonzero
scalar.
The above operations also hold for columns and may be restated as
ele-
mentary column operations
by replacing the word “row” by “column” wherever
they occur.
∈
M
m
×
n
(
R
) can be reduced by
application of elementary row and column operations to an
m
It is a fact that any nonzero
M
×
n
matrix of one
of the following forms: (
I
m
,
0),
I
n
0
00
,
I
n
, where the 0's denote
that the matrix has only zero entries in those positions, and the
I
j
's are identity
matrices of the given size for
j
=
m,n,r
. Since the
rank
of a matrix is equal to
the order of the largest nonzero minor, then in the above four cases, the ranks
are
m,n,r,
and
n
, respectively.
Matrices in the form given above are in what is called
reduced row echelon
form
, which is a matrix that has the following properties.
,
I
r
0
1. All zero rows are in the bottom position(s).
2.
Reading left to right, the first nonzero element in a nonzero row is a 1,
which is called a
leading
1.
3. For
j>
2, if there exists a leading 1 in row
j
, then it appears to the right
of a leading 1 in row
j
−
1.
4. Any column containing a leading 1 has all other elements equal to zero.
When applied to a system of
m
linear equations in
n
unknowns, there is an
equivalent formulation in which the matrix representation, called the
augmented
matrix
, has reduced row echelon form. In practice, the reduction of a system of
linear equations to its reduced row echelon form is calculated via the employment
of Gaussian elimination, discussed earlier.
Search WWH ::
Custom Search