Let's consider square matrix
(n is a dimension of the matrix E and fixed (for example n = 4 or n=5)). Matrix entries satisfy following conditions:
The task is to generate all matrices E. My question is how to do that? Is there any common approach or algorithm? Is that even possible? What to start with?
A naive solution to consider is to generate every possible n
-by-n
matrix E
where each component is a nonnegative integer no greater than n
, then take from those only the matrices that satisfy the additional constraints. What would be the complexity of that?
Each component can take on n + 1
values, and there are n^2
components, so there are O((n+1)^(n^2))
candidate matrices. That has an insanely high growth rate.
Link: WolframAlpha analysis of (n+1)^(n^2)
I think it's safe to safe that this not a feasible approach.
A better solution follows. It involves a lot of math.
Let S
be the set of all matrices E
that satisfy your requirements. Let N = {1, 2, ..., n}
.
Definitions:
Let a metric on N
to have the usual definition, except with the requirement of symmetry omitted.
Let I
and J
partition the set N
. Let D(I,J)
be the n
x n
matrix that has D_ij = 1
when i
is in I
and j
is in J
, and D_ij = 0
otherwise.
Let A
and B
be in S
. Then A
is adjacent to B
if and only if there exist I
and J
partitioning N
such that A + D(I,J) = B
.
We say A
and B
are adjacent if and only if A
is adjacent to B
or B
is adjacent to A
.
Two matrices A
and B
in S
are path-connected if and only if there exists a sequence of adjacent elements of S
between them.
Let the function M(E)
denote the sum of the elements of matrix E
.
Lemma 1:E = D(I,J)
is a metric on N
.
Proof:
This is a trivial statement except for the case of an edge going fromI
toJ
. Leti
be inI
andj
be inJ
. ThenE_ij = 1
by definition ofD(I,J)
. Letk
be inN
. Ifk
is inI
, thenE_ik = 0
andE_kj = 1
, soE_ik + E_kj >= E_ij
. Ifk
is inJ
, thenE_ik = 1
andE_kj = 0
, soE_ij + E_kj >= E_ij
.
Lemma 2:
Let E
be in S
such that E != zeros(n,n)
. Then there exist I
and J
partitioning N
such that E' = E - D(I,J)
is in S
with M(E') < M(E)
.
Proof:
Let(i,j)
be such thatE_ij > 0
. LetI
be the subset ofN
that can be reached fromi
by a directed path of cost0
.I
cannot be empty, becausei
is inI
.I
cannot beN
, becausej
is not inI
. This is becauseE
satisfies the triangle inequality andE_ij > 0
.Let
J = N - I
. ThenI
andJ
are both nonempty and partitionN
. By the definition ofI
, there does not exist any(x,y)
such thatE_xy = 0
andx
is inI
andy
is inJ
. ThereforeE_xy >= 1
for allx
inI
andy
inJ
.Thus
E' = E - D(I,J) >= 0
. ThatM(E') < M(E)
is obvious, because all we have done is subtract from elements ofE
to getE'
. Now, sinceE
is a metric onN
andD(I,J)
is a metric onN
(by Lemma 1) andE >= D(I,J)
, we haveE'
is a metric onN
. ThereforeE'
is inS
.
Theorem:
Let E
be in S
. Then E
and zeros(n,n)
are path-connected.
Proof (by induction):
IfE = zeros(n,n)
, then the statement is trivial.Suppose
E != zeros(n,n)
. LetM(E)
be the sum of the values inE
. Then, by induction, we can assume that the statement is true for any matrixE'
havingM(E') < M(E)
.Since
E != zeros(n,n)
, by Lemma 2 we have someE'
inS
such thatM(E') < M(E)
. Then by the inductive hypothesisE'
is path-connected tozeros(n,n)
. ThereforeE
is path-connected tozeros(n,n)
.
Corollary:
The set S
is path-connected.
Proof:
LetA
andB
be inS
. By the Theorem,A
andB
are both path-connected tozeros(n,n)
. ThereforeA
is path-connected toB
.
The Corollary tells us that everything in S
is path-connected. So an effective way to discover all of the elements of S
is to perform a breadth-first search over the graph defined by the following.
S
are the nodes of the graphGiven a node E
, you can find all of the (potentially) unvisited neighbors of E
by simply enumerating all of the possible matrices D(I,J)
(of which there are 2^n
) and generating E' = E + D(I,J)
for each. Enumerating the D(I,J)
should be relatively straightforward (there is one for every possible subset I
of D
, except for the empty set and D
).
Note that, in the preceding paragraph, E
and D(I,J)
are both metrics on N
. So when you generate E' = E + D(I,J)
, you don't have to check that it satisfies the triangle inequality - E'
is the sum of two metrics, so it is a metric. To check that E'
is in S
, all you have to do is verify that the maximum element in E'
does not exceed n
.
You can start the breadth-first search from any element of S
and be guaranteed that you won't miss any of S
. So you can start the search with zeros(n,n)
.
Be aware that the cardinality of the set S
grows extremely fast as n
increases, so computing the entire set S
will only be tractable for small n
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With