Information Technology Reference
In-Depth Information
10.24 Consider the function
f
(
n
)
3
n
2
n
2
whose value is the product
PAQ
of three
PAQ
:
R
→R
n
n
matrices
P
,
A
,and
Q
.Let
P
and
Q
be permutation matrices whose entries serve
as control inputs. Show that
f
(
n
)
×
PAQ
is transitive of order
n
2
.
10.25 The matrix inversion function
f
(
n
)
n
2
n
2
R
→R
maps a non-singular
n
×
n
matrix
M
−
1
:
to its inverse. (See Section
6.3
.) Show that
f
(
n
)
R
M
−
1
is
(
2,
n
2
,
n
,
n/
2
)
-
over the ring
independent.
Hint:
Show that
f
(
2
n
)
M
−
1
contains as a subfunction the function
f
(
n
)
n
2
defined in Problem
10.24
. In this connection consider the following identity, which
holds when the
n
3
n
2
PAQ
:
R
→R
n
matrices
R
and
S
are non-singular:
M
=
RA
0
×
−
1
=
R
−
1
R
−
1
AS
−
1
−
S
−
1
S
0
PEBBLING SUPERCONCENTRATORS
10.26 Show that the graph consisting of two
n
=
2
d
-input FFT graphs connected back
to back (as shown in Fig.
10.24
with the second FFT graph reversed) is a supercon-
centrator. (Valiant [
343
]hasshowntheexistenceof
n
-superconcentrators with
O
(
n
)
vertices.)
Hint:
Reason that there are unique vertex-disjoint paths from any
r
input vertices of
this graph to any
r
consecutive vertices that are simultaneously outputs of the first
FFT graph and the inputs to the reversed FFT graph. The first and last vertices are
consecutive.
10.27 Prove that to pebble any
S
+
1outputsofan
n
-superconcentrator,
S
+
1
≤
n
,froman
initial placement of
S
pebbles requires that at least
n
−
S
different inputs be pebbled.
Hint:
Suppose that at most
n
(
S
+
1
)
inputs are pebbled from an initial placement
of
S
pebbles to pebble
S
+
1 outputs. Can you reason from the superconcentration
−
Figure 10.24
Two back-to-back FFT graphs form a superconcentrator.
Search WWH ::
Custom Search