Question about feedback networks and the number of possible feedback paths.

[Dario Sanfilippo]

Hello everybody.

I'm an electronic music sound artist whose research is focused on
music systems based on audio feedback networks. I'm trying to better
understand how things work, so I'd like to know more about the
structure and possible relations in these systems. Namely, I'm looking
for a formula to obtain all possible feedback loops in a feedback
network. For example, let's consider a fully-connected network with 8
microphones {1, 2, 3, 4, 5, 6, 7, 8} and 8 loudspeaker {a, b, c, d, e,
f, g, h} working simultaneously, an 8x8 matrix where each microphone
goes into all the loudspeakers, and each loudspeaker is fed back into
all the microphones. Let's assume that the origin of the feedback path
is necessary one of the inputs, thus we can exclude all the other
feedback paths. A path can be defined as the running through nodes
(back and forth from inputs to outputs) until the feedback path is
closed back into itself, where we have no repetition of nodes except
for the first one and the last one. (For example: 3-a-1-h-3, while 3-
a-1-a-3 is not to be considered.) Also, it is possible to define
different groups of paths according to their lengths, and the length
can be defined as the number of nodes covered in the path. If I'm not
wrong, in a fully-connected matrix of (N-inputs)x(M-outputs), the
longest length for a path is 2N, while the shortest one is 2. And for
each length, it should be possible to have N*M different paths. Thus,
the number I'm looking for should be (2N-1)*N*M=960. Do you know how
this could formally be explained with combinatorics? Thank you so much
for you help.

All the best,
Dario

[tirri...@gmail.com]

Errata corrige: in order for the path to go back to the origin we need a lenght which is an even number > 0: 2N/2. Thus the preview calculus should be N^2*M=512.

[duncan smith]

It appears that you are looking for simple cycles in a bipartite graph.
I have no immediate solution, but you might find it useful to conduct a
search using these terms.

If you are only concerned with situations where every microphone is
collected to every speaker then the problem is much simpler. Each simple
cycle of length n from a given microphone can be specified as a list of
n/2 + 1 microphones and a list of n/2 speakers. The first and last
microphones are the same, so the number of distinct cycles of length n
is equal to the number of ways you can list n/2 (of say M) microphones
and n/2 (of say S) speakers.

C(M,n/2) * (n/2)! * C(S,n/2) * (n/2)!

# with a little Python / gmpy

>>> import gmpy
>>> def numcycles(n, M, S):
if n % 2 == 1:
return 0
return gmpy.comb(M,n/2) * gmpy.fac(n/2) * gmpy.comb(S,n/2) * gmpy.fac(n/2)

>>> cycles = [int(numcycles(n,8,8)) for n in range(20)]
>>> cycles
[1, 0, 64, 0, 3136, 0, 112896, 0, 2822400, 0, 45158400, 0, 406425600, 0,
1625702400, 0, 1625702400, 0, 0, 0]


How you want to interpret the single path for n = 0 is up to you
(range(20) is a list of integers from 0 to 19).

Other questions can be answered in a similar fashion (i.e. with
reference to 2 lists and the number of choices available for them given
any constraints).

Duncan

[tirri...@gmail.com]

Thank you so much for your help, Duncan!

All the best,
Dario

[tirri...@gmail.com]

Hi, Duncan. Sorry if I get back to this thread after so much time but only recently I started again to work on it.

> It appears that you are looking for simple cycles in a bipartite graph.
>
> I have no immediate solution, but you might find it useful to conduct a
>
> search using these terms.

Yes, I think that the bipartite graph is what that kind of network can be referred to.

>
>
>
> If you are only concerned with situations where every microphone is
>
> collected to every speaker then the problem is much simpler.

Yes, let's stick on this situation for the moment.

> Each simple
>
> cycle of length n from a given microphone can be specified as a list of
>
> n/2 + 1 microphones and a list of n/2 speakers. The first and last
>
> microphones are the same, so the number of distinct cycles of length n
>
> is equal to the number of ways you can list n/2 (of say M) microphones
>
> and n/2 (of say S) speakers.
>
>
>
> C(M,n/2) * (n/2)! * C(S,n/2) * (n/2)!

Ok. If I'm not wrong, from the results of your code it seems like these are permutations of each of the two sets M and S and then the multiplication between them. Just to be clear, we're talking about lists where the order matters and where we have no repetitions, correct? So, for each set, P(SET,n/2)=SET!/(SET-n/2)!, where SET is the number of elements in our set and n (even and <= M+S) is the length of a closed path. The fact is that since I will practically work with continuous flows, I should just take into account lists which have a different sequence, no matter what node they start from. For example, let's consider a set M{1,2,3,4} and a set S{a,b,c,d}. The paths 1>a>2>b>3>c>4>d(>1) and 2>b>3>c>4>d>1>a(>2) should not be considered as different loops. I think that in the numbers resulting from your calculation there are also the loops starting from the speakers, like a>2>b>3>c>4>d>1(>a). What I wonder is whether: dividing the numbers resulting from your calculation by 2 we can that way exclude the lists starting from the elements in the set S, and if, again, dividing what results from the first division by n/2 (the number of possible origins in the path) we can thus obtain only the number of different closed sequences apart from their origin.

Thanks, Duncan, and thanks to anybody else who can help me to clarify this curiosity. I also hope what I wanted to express was clear enough.

Best,
Dario