Information Technology Reference
In-Depth Information
It can be expressed as follows:
⎡
⎣
⎤
⎦
⎡
⎣
⎤
⎦
⎡
⎣
⎤
⎦
x
1
x
2
x
3
x
4
1234
5678
9 0 1 2
13
17
18
19
20
=
14
15
16
Solving a linear system
, when it is possible, consists of finding values for
x
given values for
A
and
b
.(SeeSection
6.6
.)
Consider the set of
m
×
n
matrices whose entries are drawn from a ring
R
.The
matrix
addition function
f
(
m
,
n
)
A
+
B
2
mn
mn
on two
m
:
R
→R
×
n
matrices
A
=[
a
i
,
j
]
and
B
=[
b
i
,
j
]
generates a matrix
C
=
f
(
m
,
n
)
A
+
B
(
A
,
B
)=
A
+
m
,
n
B
=[
c
i
,
j
]
,where
+
m
,
n
is the infix matrix
addition operator and
c
i
,
j
is defined as
c
i
,
j
=
a
i
,
j
+
b
i
,
j
The straight-line program based on this equation uses one instance of the ring addition op-
erator
+
for each entry in
C
. It follows that over the basis
,
C
+
(
f
(
m
,
n
)
{
+
}
A
+
B
)=
mn
and
D
+
(
f
(
m
,
n
)
A
+
B
)=
1. Two special cases of matrix addition are the addition of square matrices
(
m
=
n
), denoted
+
n
, and the addition of row or column vectors that are either 1
×
n
or
m
×
1matrices.
The
matrix multiplication function
f
(
n
)
A×B
(
m
+
p
)
n
mp
multiplies an
m
:
R
→R
×
n
matrix
A
=[
a
i
,
j
]
by an
n
×
p
matrix
B
=[
b
i
,
j
]
to produce the
m
×
p
matrix
C
=
f
(
n
)
A×B
(
A
,
B
)=
A
×
n
B
=[
c
i
,
j
]
,where
n
c
i
,
j
=
a
i
,
k
∗
b
k
,
j
(6.1)
k
=
1
and
×
n
is usually dropped
when the dimensions of the matrices are understood. The
standard matrix multiplication
algorithm
for multiplying an
m
×
n
is the infix matrix multiplication operator. The subscript on
p
matrix
B
forms
mp
inner products
of the kind shown in equation (
6.1
). Thus, it uses
mnp
instances of the ring multiplication
operator and
m
(
n
×
n
matrix
A
by an
n
×
1
)
p
instances of the ring addition operator.
A fast algorithm for matrix multiplication is given in Section
6.3.1
. It is now straightfor-
ward to show the following result. (See Problem
6.4
.)
−
THEOREM
6.2.1
Let
M
n×n
be the set of
n × n
matrices over a commutative ring
R
.The
system
M
n×n
=(
M
n×n
,
+
n
,
×
n
,0
n
,
I
n
)
,where
+
n
and
×
n
are the matrix addition and
multiplication operators and
0
n
and
I
n
are the
n
×
n
zero and identity matrices, is a ring.
M
n×n
is not a commutative ring because matrix multiplication is not
commutative. For example, the following two matrices do not commute, that is,
AB
The ring of matrices
=
BA
:
A
=
01
10
B
=
10
0
−
1
m
matrix
A
is a sum of scalar
products of the rows in this subset. A linear combination is
non-zero
if the sum of the scalar
A
linear combination
of a subset of the rows of an
n
×
Search WWH ::
Custom Search