## Counting problem of combinations of matrix.

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

### Counting problem of combinations of matrix.

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 ),

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 ).

After repetition, the final picture would be,

**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?