Intereting Posts

Topologies in a Riemannian Manifold
Resolution of Singularities: Base Point
For subspaces, if $N\subseteq M_1\cup\cdots\cup M_k$, then $N\subseteq M_i$ for some $i$?
Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?
An example of a function uniformly continuous on $\mathbb{R}$ but not Lipschitz continuous
General McNugget problem
Show that $p \Rightarrow (\neg(q \land \neg p))$ is a tautology
Concave function divided by a convex function. What is the result?
Infinitely many simple groups with conditions on order?
Circle on Riemann sphere
Does validity of Bezout identity in integral domain implies the domain is PID?
What does this double sided arrow mean?
Residue at essential singularity
Prove this number fact
How to derive the Dirichlet-multinomial?

Suppose $X$ is a $k$-regular graph with adjacency matrix $A$. I wish to show that if $k$ has multiplicity $1$ as an eigenvalue of $A$ then $X$ is connected.

By way of contradiction I assume that X is not connected. Now A can be block diagonalized, $A=diag(A_1,A_2\cdots A_t)$ where each $A_i$ is the adjacency matrix of a connected component and is of order $n_i\times n_i$. Furthermore if $v$ is the eigenvector corresponding to $k$ then the first $n_1$ entries in $Av$ are obtained from linear combinations of the columns $A_1$, the next $n_2$ entries from linear combinations of the columns of $A_2$ and so on. At this point I am stuck. Ideally I would like to construct two linearly independent eigenvectors corresponding to $k$ to derive a contradiction. Its not clear to me how can I do that.

Can someone help please.

- Is this true: any bipartite graph with unbalanced vertex parity is not Hamiltonian?
- How to prove that a connected graph with $|V| -1= |E|$ is a tree?
- A problem with 26 distinct positive integers
- What are good books to learn graph theory?
- Could one be a friend of all?
- Decomposition of graph to cycle and cut space

PS: My intuition is that the vector consisting of first $n_1$ entries of $v$ followed by zeroes, is an eigenvector, and $n_1$ zeroes followed by the corresponding $n_2$ entries of $v$, followed by zeroes is another eigenvector, independent of the first. Is this correct?

- Show that the zero set of $f$ is an orientable submanifold of $\Bbb R^{n+1}$.
- Strict Inequality in Homogenous LMI
- Can an infinite sum of irrational numbers be rational?
- $A \in {M_n}$ is normal.why the range of $A$ and ${A^*}$ are the same?.
- The relation between axes of 3D rotations
- Etymology of the word “normal” (perpendicular)
- Are vector spaces and their double duals in fact equal?
- Prove: Square Matrix Can Be Written As A Sum Of A Symmetric And Skew-Symmetric Matrices
- Find a basis for a solution set of a linear system
- Why does a diagonalization of a matrix B with the basis of a commuting matrix A give a block diagonal matrix?

Your intuition is totally correct.

$v = \mathbf{1}$ is an eigenvector to eigenvalue $k$, since $A \mathbf{1} = k \mathbf{1}$.

Now, let $v_i$ denote the characteristic function of the $i$’th connected component, i.e., $v_i(x)$ is $1$ for all vertices $x$ within the $i$’th component and $0$ else, thus, it is $\mathbf{1} = \sum_{i=1}^t v_i$.

For any $i = 1, \ldots, t$ you get that $A v_i = k v_i$.

Thus, as you argued, if $X$ is not connected, then you can use the block diagonalized form to show that the $v_i$’s are $t>1$ distinct (even orthogonal) eigenvectors to the eigenvalue $k$.

Clearly, $\mathbf{1}$ is still an eigenvector, but it is composed by multiple other eigenvectors that form the $t$-dimensional eigenspace to the eigenvalue $k$.

Further, you do not even need the block diagonalized form, although it clearifies what’s going on. In general, right-multiplication to the adjacency matrix with a vector $w \in \{0,1\}^n$ gives a vector that collects amount $1$ from all $1$-valued neighbors. So, the positions of the zero-entries in $A w$ match the positions of the zero-entries in $w$ if and only if $w$ is a characteristic vector of some connected component.

- Find the conectives of a composed proposition given a a true table
- Are regular languages necessarily deterministic context-free languages?
- Find the least value of x which when divided by 3 leaves remainder 1, …
- Why do people simulate with Brownian motion instead of “Intuitive Brownian Motion”?
- Which number its greater $\pi^3$ or $3^\pi$?
- Independence and Events.
- Difference between a proposition and an assertion
- Proof of rank-nullity via the first isomorphism theorem
- Existence of non-constant continuous functions with infinitely many zeros
- conformally equivalent flat tori
- Can Euler's identity be extended to quaternions?
- Proving the integral of an inverse function
- Factorization of a map between CW complexes
- prove there is no smallest positive rational number
- What is wrong with this derivation of $\frac{d}{dx}x^2$?