Square graph - Revision history

Vipul: /* Normalized Laplacian matrix */

2014-05-26T00:20:38Z

Normalized Laplacian matrix

← Older revision		Revision as of 00:20, 26 May 2014
Line 174:		Line 174:
	\| minimal polynomial \|\| <math>t(t - 1)(t - 2)</math> \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t(t - 1)(t - 2)</math> (independent of <math>m,n</math> as long as <math>m + n > 2</math>)		\| minimal polynomial \|\| <math>t(t - 1)(t - 2)</math> \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t(t - 1)(t - 2)</math> (independent of <math>m,n</math> as long as <math>m + n > 2</math>)
	\|-		\|-
	\| rank of normalized Laplacian matrix \|\| 3 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n - 1 = 2 + 2 - 1 = 5</math>		\| rank of normalized Laplacian matrix \|\| 3 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n - 1 = 2 + 2 - 1 = 3</math>
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (2 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 0 (1 time), 2 (1 time), 1 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times)		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (2 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 0 (1 time), 2 (1 time), 1 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times)

Vipul: /* Normalized Laplacian matrix */

2014-05-26T00:18:50Z

Normalized Laplacian matrix

← Older revision		Revision as of 00:18, 26 May 2014
Line 172:		Line 172:
	\| characteristic polynomial \|\| <math>t(t - 2)(t - 1)^2</math>\|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t(t - 2)(t - 1)^{m+n-2}</math>		\| characteristic polynomial \|\| <math>t(t - 2)(t - 1)^2</math>\|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t(t - 2)(t - 1)^{m+n-2}</math>
	\|-		\|-
	\| minimal polynomial \|\| <math>t(t - 1)(t - 2)</math> \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t(t - 1)(t - 2)</math>		\| minimal polynomial \|\| <math>t(t - 1)(t - 2)</math> \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t(t - 1)(t - 2)</math> (independent of <math>m,n</math> as long as <math>m + n > 2</math>)
	\|-		\|-
	\| rank of normalized Laplacian matrix \|\| 3 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n - 1 = 2 + 2 - 1 = 5</math>		\| rank of normalized Laplacian matrix \|\| 3 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n - 1 = 2 + 2 - 1 = 5</math>

Vipul: /* Normalized Laplacian matrix */

2014-05-26T00:16:47Z

Normalized Laplacian matrix

← Older revision		Revision as of 00:16, 26 May 2014
Line 176:		Line 176:
	\| rank of normalized Laplacian matrix \|\| 3 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n - 1 = 2 + 2 - 1 = 5</math>		\| rank of normalized Laplacian matrix \|\| 3 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n - 1 = 2 + 2 - 1 = 5</math>
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (2 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), 2 (1 time), 1 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times)		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (2 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 0 (1 time), 2 (1 time), 1 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times)
	\|}		\|}

Vipul: /* Normalized Laplacian matrix */

2014-05-26T00:14:21Z

Normalized Laplacian matrix

← Older revision		Revision as of 00:14, 26 May 2014
Line 170:		Line 170:
	! Algebraic invariant !! Value !! Explanation		! Algebraic invariant !! Value !! Explanation
	\|-		\|-
	\| characteristic polynomial \|\| <math>t(t - 2)(t - 1)^2</math>\|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t(t - ~~(m + n)/\sqrt{mn}~~)(t ~~- \sqrt{m/n})^{n~~-1~~}(t-\sqrt{n/m}~~)^{m-1}</math>		\| characteristic polynomial \|\| <math>t(t - 2)(t - 1)^2</math>\|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t(t - 2)(t - 1)^{m+n-2}</math>
	\|-		\|-
	\| minimal polynomial \|\| <math>t(t - 1)(t - 2)</math> \|\| As complete bipartite graph <math>K_{m,m}, m = 2</math>: <math>t(t - 1)(t - 2)</math>		\| minimal polynomial \|\| <math>t(t - 1)(t - 2)</math> \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t(t - 1)(t - 2)</math>
	\|-		\|-
	\| rank of normalized Laplacian matrix \|\| 3 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n - 1 = 2 + 2 - 1 = 5</math>		\| rank of normalized Laplacian matrix \|\| 3 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n - 1 = 2 + 2 - 1 = 5</math>
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (2 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), ~~<math>(m + n)/\sqrt{mn} =~~ 2~~</math>~~ (1 time), 1 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times)		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (2 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), 2 (1 time), 1 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times)
	\|}		\|}

Vipul: /* Normalized Laplacian matrix */

2014-05-25T23:16:10Z

Normalized Laplacian matrix

← Older revision		Revision as of 23:16, 25 May 2014
Line 176:		Line 176:
	\| rank of normalized Laplacian matrix \|\| 3 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n - 1 = 2 + 2 - 1 = 5</math>		\| rank of normalized Laplacian matrix \|\| 3 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>m + n - 1 = 2 + 2 - 1 = 5</math>
	\|-		\|-
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (2 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>(m + n)/\sqrt{mn} = 2</math> (1 time), 1 (~~2 times:~~ <math>n - 1 = 2 - ~~1 = 1</math> time as <math>\sqrt{m/n}</math> and <math>m - 1~~ = 2 ~~- 1 = 1</math> time as <math>\sqrt{n/m}~~</math>)		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 2 (1 time), 1 (2 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>(m + n)/\sqrt{mn} = 2</math> (1 time), 1 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times)
	\|}		\|}

Vipul: /* Algebraic theory */

2014-05-25T22:46:21Z

Algebraic theory

@@ Line 157: / Line 157: @@
 |-
 | eigenvalues (roots of characteristic polynomial) || 0 (1 time), 4 (1 time), 2 (2 times) || As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>m + n = 4</math> (1 time), <math>m = n = 2</math> (2 times: <math>n - 1 = 2 - 1 = 1</math> times as <math>m</math> and <math>m - 1 = 2 - 1 = 1</math> times as <math>m</math>)
 |}

Vipul: /* Laplacian matrix */

2014-05-25T22:42:47Z

Laplacian matrix

← Older revision		Revision as of 22:42, 25 May 2014
Line 144:		Line 144:

	<math>\begin{pmatrix} 2 & 0 & -1 & -1 \\0 & 2 & -1 & -1 \\ -1 & -1 & 2 & 0 \\ -1 & -1 & 0 & 2 \\\end{pmatrix}</math>		<math>\begin{pmatrix} 2 & 0 & -1 & -1 \\0 & 2 & -1 & -1 \\ -1 & -1 & 2 & 0 \\ -1 & -1 & 0 & 2 \\\end{pmatrix}</math>

			The matrix is uniquely defined up to permutation by conjugations. Below are some algebraic invariants associated with the matrix:

			{\| class="sortable" border="1"
			! Algebraic invariant !! Value !! Explanation
			\|-
			\| characteristic polynomial \|\| <math>t(t - 4)(t - 2)^2</math>\|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: <math>t(t - (m + n))(t - m)^{n-1}(t-n)^{m-1}</math>
			\|-
			\| minimal polynomial \|\| <math>t(t - 2)(t - 4)</math> \|\| As complete bipartite graph <math>K_{m,m}, m = 2</math>: <math>t(t - m)(t - 2m)</math>
			\|-
			\| rank of Laplacian matrix \|\| 3 \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: <math>m + n - 1 = 2 + 2 - 1 = 3</math>
			\|-
			\| eigenvalues (roots of characteristic polynomial) \|\| 0 (1 time), 4 (1 time), 2 (2 times) \|\| As complete bipartite graph <math>K_{m,n}, m = n = 3</math>: 0 (1 time), <math>m + n = 4</math> (1 time), <math>m = n = 2</math> (2 times: <math>n - 1 = 2 - 1 = 1</math> times as <math>m</math> and <math>m - 1 = 2 - 1 = 1</math> times as <math>m</math>)
			\|}

	==Realization==		==Realization==

Vipul: /* Algebraic theory */

2014-05-25T22:40:09Z

Algebraic theory

← Older revision		Revision as of 22:40, 25 May 2014
Line 114:		Line 114:

	==Algebraic theory==		==Algebraic theory==

			===Adjacency matrix===

	The adjacency matrix is:		The adjacency matrix is:
Line 119:		Line 121:
	<math>\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\\end{pmatrix}</math>		<math>\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\\end{pmatrix}</math>

	It can alternately be written as:		It can alternately be written in the following form, which is more computationally convenient because it clearly identifies blocks of 0s and 1s:

	<math>\begin{pmatrix} 0 & 0 & 1 & 1 \\0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\1 & 1 & 0 & 0 \\\end{pmatrix}</math>		<math>\begin{pmatrix} 0 & 0 & 1 & 1 \\0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\1 & 1 & 0 & 0 \\\end{pmatrix}</math>
Line 136:		Line 138:
	\| eigenvalues (roots of characteristic polynomial) \|\| 0 (2 times), 2 (1 time), -2 (1 time)\|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 0 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times), <math>\sqrt{mn} = \sqrt{(2)(2)} = 2</math> (1 time), <math>-\sqrt{mn} = -\sqrt{(2)(2)} = -2</math> (1 time)		\| eigenvalues (roots of characteristic polynomial) \|\| 0 (2 times), 2 (1 time), -2 (1 time)\|\| As complete bipartite graph <math>K_{m,n}, m = n = 2</math>: 0 (<math>m + n - 2 = 2 + 2 - 2 = 2</math> times), <math>\sqrt{mn} = \sqrt{(2)(2)} = 2</math> (1 time), <math>-\sqrt{mn} = -\sqrt{(2)(2)} = -2</math> (1 time)
	\|}		\|}

			===Laplacian matrix===

			The [[Laplacian matrix]] is as follows:

			<math>\begin{pmatrix} 2 & 0 & -1 & -1 \\0 & 2 & -1 & -1 \\ -1 & -1 & 2 & 0 \\ -1 & -1 & 0 & 2 \\\end{pmatrix}</math>

	==Realization==		==Realization==

Vipul at 21:01, 29 May 2012

2012-05-29T21:01:18Z

← Older revision		Revision as of 21:01, 29 May 2012
Line 3:		Line 3:
	==Definition==		==Definition==

	This [[undirected graph]] is defined in the following equivalent ways:		This [[undirected graph]], called the '''square graph''', is defined in the following equivalent ways:

	# It is the [[cycle graph]] on 4 vertices, denoted <math>C_4</math>.		# It is the [[cycle graph]] on 4 vertices, denoted <math>C_4</math>.

Vipul: moved Cycle graph:C4 to Square graph

2012-05-29T21:00:57Z

moved Cycle graph:C4 to Square graph

← Older revision	Revision as of 21:00, 29 May 2012
(No difference)