Counting problem of combinations of matrix.

Arrangements, combinations and permutations, probability, ...
Post Reply
jim
Posts: 2
Joined: Tue May 05, 2015 10:50 am

Counting problem of combinations of matrix.

Post by jim » Tue May 05, 2015 11:04 am

Given, a symmetric $n*n$ matrix $G$ with 0,1 entries. Each row of has same number of 1. $G$ is arranged in a certain order using a rule. The rule is described below-
$G$ is partitioned in to two sub matrices based on the adjacency of $n$ th column/row(column=row since it is a symmetric matrix).

e.g. n=10 for below matrix,10th vertex partitioned the whole matrix into 2 parts(matrices ),

Image


Vertices which are adjacent to 10th vertex(7,8,9 in one part) and vertices which are not (1,2,3,4,5,6 in other part ).

Image

After repetition, the final picture would be,





Image


**Question:** If $H$ is a permuted $G$, (i.e. $H=P G$ ,where P is a permutation matrix), following the given rule above, how many combinations require to check(minimum number) to ensure that H is a permuted G?
i.e if $H$ is not a permuted $G$,how many combinations require to check(minimum number) to ensure that H is not a permuted G?

Post Reply