Cryptography Reference
In-Depth Information
for all 1
≤
i<j
≤
n
. If we also have the condition
v
i
,v
i
=
1 then the basis is called
orthonormal
.
=
j
=
1
λ
j
v
j
then
n
.If
v
Lemma A.10.5
Let
{
v
1
,...,
v
n
}
be an orthogonal basis for
R
=
j
=
1
λ
j
2
2
.
v
v
j
then it is extremely easy to decompose an
arbitrary vector
w
over the basis. The representation is
If one has an orthogonal basis
{
v
1
,...,
v
n
}
n
w
,
v
i
w
=
v
i
.
v
i
,
v
i
i
=
1
This is simpler and faster than solving the linear system using Gaussian elimination.
If
V
n
is a subspace then the
orthogonal complement
is
V
⊥
={
n
:
⊆ R
w
∈ R
w
,
v
=
. The dimension of
V
⊥
is
n
0 for all
v
∈
V
}
−
dim(
V
). Given a basis
{
v
1
,...,
v
m
}
for
V
for
V
⊥
.The
orthogonal
(where
m
=
dim(
V
)
<n
) one can compute a basis
{
v
m
+
1
,...,
v
n
}
n
to a subspace
V
is a linear map
P
:
n
projection
of
R
R
→
V
that is the identity on
V
and
is such that
P
(
V
⊥
)
n
then
v
V
⊥
.
={
0
}
. In other words, if
v
∈ R
−
P
(
v
)
∈
A.10.2 Gram-Schmidt orthogonalisation
Given a basis
v
1
,...,
v
n
for a vector space, the Gram-Schmidt algorithm iteratively com-
putes an orthogonal basis
v
1
,...,
v
n
(called the
Gram-Schmidt orthogonalisation
or
GSO
). The idea is to set
v
1
=
v
1
and then, for 2
≤
i
≤
n
, to compute
i
−
1
v
i
,
v
j
v
i
=
µ
i,j
v
j
where
µ
i,j
=
v
i
−
.
v
j
,
v
j
j
=
1
We discuss this algorithm further in Section
17.3
.
A.10.3 Determinants
Let
b
1
,...,
b
n
be
n
vectors in
n
. One can define the
determinant
of the sequence
b
1
,...,
b
n
(or of the matrix
B
whose rows are
b
1
,...,
b
n
) in the usual way (see Chapter 5
of Curtis [
151
] or Section VII.3 of Hungerford [
271
]).
k
Lemma A.10.6
Let
b
1
,...,
b
n
∈ k
n
.
1. Let B be the matrix whose rows are
b
1
,...,
b
n
. Then B is invertible if and only if
det(
b
1
,...,
b
n
)
=
0
.
∈ k
=
2. For λ
,
det(
b
1
,...,
b
i
−
1
,λ
b
i
,
b
i
+
1
,...,
b
n
)
λ
det(
b
1
,...,
b
n
)
.
3.
det(
b
1
,...,
b
i
−
1
,
b
i
+
b
j
,
b
i
+
1
,...,
b
n
)
=
det(
b
1
,...,
b
n
)
for i
=
j.
{
e
1
,...,
e
n
}
k
n
then
det(
e
1
,...,
e
n
)
=
4. If
are the standard unit vectors in
1
.
5. If B
1
,B
2
are square matrices then
det(
B
1
B
2
)
=
det(
B
1
) det(
B
2
)
.
6.
det(
B
)
det(
B
T
)
.
7. (Hadamard inequality)
=
|≤
i
=
1
|
det(
b
1
,...,
b
n
)
b
i
(where
b
is the Euclidean
norm).
Proof
See Theorems 16.6, 17.6, 17.15, 18.3 and 19.13 of Curtis [
151
].
