- #1

- 1,456

- 44

- I
- Thread starter Mr Davis 97
- Start date

- #1

- 1,456

- 44

- #2

mfb

Mentor

- 34,655

- 10,797

- #3

StoneTemplePython

Science Advisor

Gold Member

2019 Award

- 1,167

- 569

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:

- Replies
- 1

- Views
- 479

- Last Post

- Replies
- 3

- Views
- 1K

- Last Post

- Replies
- 2

- Views
- 1K

- Replies
- 4

- Views
- 1K

- Last Post

- Replies
- 4

- Views
- 2K

- Last Post

- Replies
- 5

- Views
- 10K

- Last Post

- Replies
- 7

- Views
- 3K

- Last Post

- Replies
- 11

- Views
- 3K

- Last Post

- Replies
- 10

- Views
- 3K

- Last Post

- Replies
- 4

- Views
- 2K