Cryptography Reference
In-Depth Information
n
m
such that
A
(
λ
x
A
linear map
is a function
A
:
k
→ k
+
µ
y
)
=
λA
(
x
)
+
µA
(
y
)
n
. Given a basis for
n
, any linear map can be represented
for all
λ,µ
∈ k
and
x
,
y
∈ k
k
as an
n
×
m
matrix
A
such that
A
(
x
)
=
x
A
. We denote the entries of
A
by
A
i,j
for
n
identity matrix
. We denote by
A
T
the
1
≤
i
≤
n,
1
≤
j
≤
m
. Denote by
I
n
the
n
×
B
T
A
T
.
A fundamental computational problem is to solve the linear system of equations
x
A
n
matrix such that (
A
T
)
i,j
=
A
j,i
.Wehave(
AB
)
T
transpose
, which is an
m
×
=
y
and it is well-known that this can be done using Gaussian elimination (see Section 6 of
Curtis [
151
] or Chapter 3 of Schrijver [
478
]).
The
rank
of an
m
=
n
matrix
A
(denoted rank(
A
)) is the maximum number of lin-
early independent rows of
A
(equivalently, the maximum number of linearly independent
columns). If
A
is an
n
×
×
n
matrix then the
inverse
of
A
, if it exists, is the matrix such that
AA
−
1
A
−
1
A
I
n
.If
A
and
B
are invertible then (
AB
)
−
1
B
−
1
A
−
1
. One can compute
=
=
=
A
−
1
using Gaussian elimination.
A.10.1 Inner products and norms
Definition
A.10.1
The
inner
product
of
two
vectors
v
=
(
v
1
,...,v
n
)
and
w
=
n
is
(
w
1
,...,w
n
)
∈ k
n
v
,
w
=
v
i
w
i
.
i
=
1
∈ R
n
is
The
Euclidean norm
or
2
-norm
of a vector
v
=
v
v
,
v
.
n
one can define the
a
-norm
of a vector
v
for any
a
More generally for
R
∈ N
as
a
=
i
=
1
|
a
1
/a
. Important special cases are the
1
-norm
v
i
=
i
=
1
|
v
v
i
|
v
i
|
and the
∞
-norm
. (The reader should not confuse the notion of norm
in Galois theory with the notion of norm on vector spaces.)
v
∞
=
max
{|
v
1
|
,...,
|
v
n
|}
∈ R
n
. Then
Lemma A.10.2
Let
v
2
≤
√
n
v
∞
≤
v
v
∞
and
v
∞
≤
v
1
≤
n
v
∞
.
n
and let
Lemma A.10.3
Let
v
,
w
∈ R
v
be the Euclidean norm.
1.
v
+
w
≤
v
+
w
.
2.
v
,
w
=
w
,
v
.
3.
v
=
0
implies
v
=
0
.
4.
|
v
,
w
| ≤
v
w
.
5. Let A be an n
×
n matrix over
R
. The following are equivalent:
n
;
(a)
x
A
=
x
for all
x
∈ R
n
;
(b)
x
A,
y
A
=
x
,
y
for all
x
,
y
∈ R
1
).
Such a matrix is called an
orthogonal matrix
.
(c) AA
T
=
I
n
(which implies
det(
A
)
2
=
Definition A.10.4
A basis
{
v
1
,...,v
n
}
for a vector space is
orthogonal
if
v
i
,v
j
=
0
