Complete bipartite graph - Revision history

Vipul: /* Normalized Laplacian matrix */

2014-05-26T00:11:53Z

Normalized Laplacian matrix

← Older revision		Revision as of 00:11, 26 May 2014
Line 130:		Line 130:
	! Algebraic invariant !! Value !! Explanation		! Algebraic invariant !! Value !! Explanation
	\|-		\|-
	\| characteristic polynomial \|\| <math>t(t - ~~(m + n)/\sqrt{mn}~~)(t - 1)^{m+n-2}</math><br>Note that when <math>m = n</math>, this simplifies to <math>t(t - 2)(t - 1)^{2(m - 1)}</math> \|\|		\| characteristic polynomial \|\| <math>t(t - 2)(t - 1)^{m+n-2}</math><br>Note that when <math>m = n</math>, this simplifies to <math>t(t - 2)(t - 1)^{2(m - 1)}</math> \|\|
	\|-		\|-
	\| minimal polynomial \|\| If <math>m + n > 2</math>: <math>t(t - 1)(t - ~~(m + n)/\sqrt{mn}~~)</math><br>If <math>m = n = 1</math>: <math>t(t - 2)</math> \|\|		\| minimal polynomial \|\| If <math>m + n > 2</math>: <math>t(t - 1)(t - 2)</math><br>If <math>m = n = 1</math>: <math>t(t - 2)</math> \|\|
	\|-		\|-
	\| rank of normalized Laplacian matrix \|\| <math>m + n - 1</math> \|\|		\| rank of normalized Laplacian matrix \|\| <math>m + n - 1</math> \|\|
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), ~~<math>(m + n)/\sqrt{mn}</math>~~ (1 time), 1 (<math>m + n - 2</math> times)<br>Note that the eigenvalue 1 disappears if <math>m = n = 1</math> \|\|		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (<math>m + n - 2</math> times)<br>Note that the eigenvalue 1 disappears if <math>m = n = 1</math> \|\|
	\|}		\|}

Vipul: /* Normalized Laplacian matrix */

2014-05-25T23:58:00Z

Normalized Laplacian matrix

← Older revision		Revision as of 23:58, 25 May 2014
Line 132:		Line 132:
	\| characteristic polynomial \|\| <math>t(t - (m + n)/\sqrt{mn})(t - 1)^{m+n-2}</math><br>Note that when <math>m = n</math>, this simplifies to <math>t(t - 2)(t - 1)^{2(m - 1)}</math> \|\|		\| characteristic polynomial \|\| <math>t(t - (m + n)/\sqrt{mn})(t - 1)^{m+n-2}</math><br>Note that when <math>m = n</math>, this simplifies to <math>t(t - 2)(t - 1)^{2(m - 1)}</math> \|\|
	\|-		\|-
	\| minimal polynomial \|\| <math>t(t - 1)(t - (m + n)/\sqrt{mn})</math> \|\|		\| minimal polynomial \|\| If <math>m + n > 2</math>: <math>t(t - 1)(t - (m + n)/\sqrt{mn})</math><br>If <math>m = n = 1</math>: <math>t(t - 2)</math> \|\|
	\|-		\|-
	\| rank of normalized Laplacian matrix \|\| <math>m + n - 1</math> \|\|		\| rank of normalized Laplacian matrix \|\| <math>m + n - 1</math> \|\|
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), <math>(m + n)/\sqrt{mn}</math> (1 time), 1 (<math>m + n - 2</math> times) \|\|		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), <math>(m + n)/\sqrt{mn}</math> (1 time), 1 (<math>m + n - 2</math> times)<br>Note that the eigenvalue 1 disappears if <math>m = n = 1</math> \|\|
	\|}		\|}

Vipul: /* Laplacian matrix */

2014-05-25T23:41:20Z

Laplacian matrix

← Older revision		Revision as of 23:41, 25 May 2014
Line 112:		Line 112:
	\| characteristic polynomial \|\| <math>t(t - (m + n))(t - m)^{n-1}(t-n)^{m-1}</math> \|\|		\| characteristic polynomial \|\| <math>t(t - (m + n))(t - m)^{n-1}(t-n)^{m-1}</math> \|\|
	\|-		\|-
	\| minimal polynomial \|\| If <math>m \ne n</math>: <math>t(t - m)(t - n)(t - (m + n))</math><br>If <math>m = n</math>: <math>t(t - m)(t - 2m)</math> \|\|		\| minimal polynomial \|\| If <math>m \ne n</math> and both are greater than 1: <math>t(t - m)(t - n)(t - (m + n))</math><br>If <math>m = n > 1</math>: <math>t(t - m)(t - 2m)</math><br>If <math>m = 1, n > 1</math>: <math>t(t - 1)(t - (n + 1))</math><br>If <math>m > 1, n = 1</math>: <math>t(t - 1)(t - (m + 1))</math> \|\|
	\|-		\|-
	\| rank of Laplacian matrix \|\| <math>m + n - 1</math> \|\|		\| rank of Laplacian matrix \|\| <math>m + n - 1</math> \|\|
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), <math>m + n</math> (1 time), <math>m</math> (<math>n - 1</math> times), <math>n</math> (<math>m - 1</math> times) \|\|		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), <math>m + n</math> (1 time), <math>m</math> (<math>n - 1</math> times), <math>n</math> (<math>m - 1</math> times).<br>If <math>m = 1</math>, <math>n</math> disappears as an eigenvalue.<br>If <math>n = 1</math>, <math>m</math> disappears as an eigenvalue. \|\|
	\|}		\|}

Vipul: /* Adjacency matrix */

2014-05-25T23:35:10Z

Adjacency matrix

← Older revision		Revision as of 23:35, 25 May 2014
Line 90:		Line 90:
	\| [[characteristic polynomial of a graph\|characteristic polynomial]] \|\| <math>t^{m + n} - mnt^{m + n - 2} = t^{m + n - 2}(t^2 - mn)</math> \|\|		\| [[characteristic polynomial of a graph\|characteristic polynomial]] \|\| <math>t^{m + n} - mnt^{m + n - 2} = t^{m + n - 2}(t^2 - mn)</math> \|\|
	\|-		\|-
	\| [[minimal polynomial of a matrix\|minimal polynomial]] \|\| <math>t^3 - mnt = t(t^2 - mn)</math> \|\|		\| [[minimal polynomial of a matrix\|minimal polynomial]] \|\| if <math>m + n > 2</math>: <math>t^3 - mnt = t(t^2 - mn)</math><br>if <math>m = n = 1</math>: <math>t^2 - mn</math> \|\|
	\|-		\|-
	\| rank of adjacency matrix \|\| 2 \|\|		\| rank of adjacency matrix \|\| 2 \|\|

Vipul: /* Normalized Laplacian matrix */

2014-05-25T23:17:45Z

Normalized Laplacian matrix

← Older revision		Revision as of 23:17, 25 May 2014
Line 132:		Line 132:
	\| characteristic polynomial \|\| <math>t(t - (m + n)/\sqrt{mn})(t - 1)^{m+n-2}</math><br>Note that when <math>m = n</math>, this simplifies to <math>t(t - 2)(t - 1)^{2(m - 1)}</math> \|\|		\| characteristic polynomial \|\| <math>t(t - (m + n)/\sqrt{mn})(t - 1)^{m+n-2}</math><br>Note that when <math>m = n</math>, this simplifies to <math>t(t - 2)(t - 1)^{2(m - 1)}</math> \|\|
	\|-		\|-
	\| minimal polynomial \|\| <math>t(t - 1)(t - (m + n)/\sqrt{mn})</math>		\| minimal polynomial \|\| <math>t(t - 1)(t - (m + n)/\sqrt{mn})</math> \|\|
	\|-		\|-
	\| rank of normalized Laplacian matrix \|\| <math>m + n - 1</math>		\| rank of normalized Laplacian matrix \|\| <math>m + n - 1</math> \|\|
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), <math>(m + n)/\sqrt{mn}</math> (1 time), 1 (<math>m + n - 2</math> times)		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), <math>(m + n)/\sqrt{mn}</math> (1 time), 1 (<math>m + n - 2</math> times) \|\|
	\|}		\|}

Vipul: /* Laplacian matrix */

2014-05-25T23:17:20Z

Laplacian matrix

← Older revision		Revision as of 23:17, 25 May 2014
Line 116:		Line 116:
	\| rank of Laplacian matrix \|\| <math>m + n - 1</math> \|\|		\| rank of Laplacian matrix \|\| <math>m + n - 1</math> \|\|
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), <math>m + n</math> (1 time), <math>m</math> (<math>n - 1</math> times), <math>n</math> (<math>m - 1</math> times) \|		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), <math>m + n</math> (1 time), <math>m</math> (<math>n - 1</math> times), <math>n</math> (<math>m - 1</math> times) \|\|
	\|}		\|}

Vipul: /* Laplacian matrix */

2014-05-25T23:17:07Z

Laplacian matrix

← Older revision		Revision as of 23:17, 25 May 2014
Line 114:		Line 114:
	\| minimal polynomial \|\| If <math>m \ne n</math>: <math>t(t - m)(t - n)(t - (m + n))</math><br>If <math>m = n</math>: <math>t(t - m)(t - 2m)</math> \|\|		\| minimal polynomial \|\| If <math>m \ne n</math>: <math>t(t - m)(t - n)(t - (m + n))</math><br>If <math>m = n</math>: <math>t(t - m)(t - 2m)</math> \|\|
	\|-		\|-
	\| rank of Laplacian matrix \|\| <math>m + n - 1</math>		\| rank of Laplacian matrix \|\| <math>m + n - 1</math> \|\|
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), <math>m + n</math> (1 time), <math>m</math> (<math>n - 1</math> times), <math>n</math> (<math>m - 1</math> times)		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), <math>m + n</math> (1 time), <math>m</math> (<math>n - 1</math> times), <math>n</math> (<math>m - 1</math> times) \|
	\|}		\|}

Vipul: /* Algebraic theory */

2014-05-25T23:14:00Z

Algebraic theory

@@ Line 73: / Line 73: @@
 ==Algebraic theory==
 If we order the vertices so that <math>A</math> makes up the first <math>m</math> vertices and <math>B</math> makes up the last <math>n</math> vertices, the adjacency matrix looks like the block matrix below:
@@ Line 93: / Line 95: @@
 |-
 | eigenvalues (roots of characteristic polynomial) || 0 (multiplicity <math>m + n - 2</math>), <math>\sqrt{mn}</math> (multiplicity 1), <math>-\sqrt{mn}</math> (multiplicity 1) ||
 |}

Vipul at 20:51, 29 May 2012

2012-05-29T20:51:05Z

← Older revision		Revision as of 20:51, 29 May 2012
Line 76:		Line 76:
	If we order the vertices so that <math>A</math> makes up the first <math>m</math> vertices and <math>B</math> makes up the last <math>n</math> vertices, the adjacency matrix looks like the block matrix below:		If we order the vertices so that <math>A</math> makes up the first <math>m</math> vertices and <math>B</math> makes up the last <math>n</math> vertices, the adjacency matrix looks like the block matrix below:

	<math>\begin{pmatrix} 0_{m \times m} E_{m \times n} \\ E_{n \times m} & 0_{n \times n}\\\end{pmatrix}</math>		<math>\begin{pmatrix} 0_{m \times m} & E_{m \times n} \\ E_{n \times m} & 0_{n \times n}\\\end{pmatrix}</math>

	Here, <math>E_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 1s for all its entries.		Here, <math>0_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 0s for all its entries and
			<math>E_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 1s for all its entries.

	We can thus compute various algebraic invariants:		We can thus compute various algebraic invariants:

Vipul: /* Adjacency matrix */

2012-05-29T20:50:31Z

Adjacency matrix

← Older revision		Revision as of 20:50, 29 May 2012
Line 18:		Line 18:
	<math>\begin{pmatrix} 0_{m \times m} & E_{m \times n} \\ E_{n \times m} & 0_{n \times n}\\\end{pmatrix}</math>		<math>\begin{pmatrix} 0_{m \times m} & E_{m \times n} \\ E_{n \times m} & 0_{n \times n}\\\end{pmatrix}</math>

	Here, <math>E_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 1s for all its entries.		Here, <math>0_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 0s for all its entries and
			<math>E_{a \times b}</math> is shorthand for the <math>a \times b</math> matrix with 1s for all its entries.

	==Particular cases==		==Particular cases==