- #1

- 1,462

- 44

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- I
- Thread starter Mr Davis 97
- Start date

- #1

- 1,462

- 44

- #2

mfb

Mentor

- 35,625

- 12,161

- #3

StoneTemplePython

Science Advisor

Gold Member

- 1,203

- 594

if you like adjacency matrices, then up to a graph isopmorphism, you can assume your ##K_n## is always in the top left corner of your adjacency matrix for ##K_m##.

In blocked form that top left ##\text{n x n }## submatrix is given by ##\mathbf J_n - \mathbf I_n## indicating that the submatrix (really, subgraph) is a complete graph, because an ##r## dimensional complete graph is specified by an adjacency matrix of ##\mathbf J_r -\mathbf I_r##

(note ##\mathbf J_r = \mathbf 1_r \mathbf 1_r^T## i.e. it indicates the all ones matrix)

- - - -

if you want to have some fun with the graph isomorphism, you can note that permutation matrices are doubly stochastic, and recall that ##\mathbf P^T = \mathbf P^{-1}## since they are orthogonal, so for any arbitrary permutation matrix ##\mathbf P## in ##\mathbb R^{\text{m x m}}## you have

##\mathbf P\big(\mathbf J_m -\mathbf I_m\big) \mathbf P^T = \mathbf P\big(\mathbf J_m\mathbf P^T\big) - \big(\mathbf P\mathbf I_m \mathbf P^T\big) = \mathbf P\big(\mathbf J_m\big) -\big(\mathbf P \mathbf P^T\big) = \mathbf J_m - \mathbf I_m##

In blocked form that top left ##\text{n x n }## submatrix is given by ##\mathbf J_n - \mathbf I_n## indicating that the submatrix (really, subgraph) is a complete graph, because an ##r## dimensional complete graph is specified by an adjacency matrix of ##\mathbf J_r -\mathbf I_r##

(note ##\mathbf J_r = \mathbf 1_r \mathbf 1_r^T## i.e. it indicates the all ones matrix)

- - - -

if you want to have some fun with the graph isomorphism, you can note that permutation matrices are doubly stochastic, and recall that ##\mathbf P^T = \mathbf P^{-1}## since they are orthogonal, so for any arbitrary permutation matrix ##\mathbf P## in ##\mathbb R^{\text{m x m}}## you have

##\mathbf P\big(\mathbf J_m -\mathbf I_m\big) \mathbf P^T = \mathbf P\big(\mathbf J_m\mathbf P^T\big) - \big(\mathbf P\mathbf I_m \mathbf P^T\big) = \mathbf P\big(\mathbf J_m\big) -\big(\mathbf P \mathbf P^T\big) = \mathbf J_m - \mathbf I_m##

Last edited:

Share:

- Replies
- 7

- Views
- 812