Intereting Posts

Infimum and supremum of the empty set
Tensor products commute with direct limits
Let $k \geq 3$; prove $2^k$ can be written as $(2m+1)^2+7(2n+1)^2$
A sequence of $n^2$ real numbers which contains no monotonic subsequence of more than $n$ terms
''Labelling discrimination'' for objects in a category
Rectangle with coordinates of all vertices Fibonacci numbers
Regular expression 00 or 11 not both
How can I prove $\lim_{n \to \infty} \int_{0}^{\pi/2} f(x) \sin ((2n+1) x) dx =0 $?
Evaluate $\int \frac 1{x^{12}+1} \, dx$
probability question on characteristic function
Invariance of residues modulo $p$
Asymptotics of a double integral: $ \int_0^{\infty}du\int_0^{\infty}dv\, \frac{1}{(u+v)^2}\exp\left(-\frac{x}{u+v}\right)$
What's the precise meaning of imaginary number?
What is the equation used to calculate a linear trendline?
In a convex Quadrilateral ABCD, $\measuredangle ABC = \measuredangle BCD = 120^{\circ}$.Prove that: $ AC + BD \ge AB + BC + CD$

Let $G$ be graph on $n$ vertices, $A$ its adjacency matrix, and $I_{n}$ the $n\times n$ identity matrix. Prove that $G$ is connected iff the matrix $(I_{n} + A)^{n-1}$ has no 0s.

My proof:

*If the graph is connected the matrix $(I_{n} + A)^{n-1}$ has no 0s.*

- How to get from Chebyshev to Ihara?
- Determine cycle from adjacency matrix
- Graph type taxonomy
- “Semidirect product” of graphs?
- How to count the no. of distinct ways in which $1,2,…,6$ can be assigned to $6$ faces of a cube?
- Tree having no vertex of degree 2 has more leaves than internal nodes

The identity matrix takes care of the non-zero values for the diagonal (otherwise the diagonals would be 0 since self-loops are disallowed in simple graphs).

If the graph is connected there must exist a path between any two vertices $u,v \in G$. $A^{n-1}_{i,j}$ represents the number of paths of length $n-1$ between any two vertices. If any $A^{n-1}_{i,j}$ would be 0, that would mean that there would not be any path connecting those vertices. Thus, the graph would be disconnected. But we assumed that it was connected

*If the matrix $(I_{n} + A)^{n-1}$ has no 0s then G is connected*

If every $(I_{n} + A)^{n-1}$ is non-zero this means that there exists at least one path of length $n – 1$ between any two vertices. If this is the case, the graph must be connected.

Is this correct?

- 5-color graph problem
- Condition number of a product of two matrices
- A closed Knight's Tour does not exist on some chessboards
- Linear Algebra, add these two matrices
- Is it true that $\sum_{k=1}^n |a_{kk}| \le \sum_{k=1}^n |\lambda_k|$ for any complex square matrix $A$?
- Integral identity graphs — smallest example
- Traces of all positive powers of a matrix are zero implies it is nilpotent
- Matrix exponential convergence
- If $a_{ij}=\max(i,j)$, calculate the determinant of $A$
- Prove that if every node in a simple graph $G$ has degree $3$ or higher, then $G$ contains a cycle with a chord.

It is not enough to check whether the $i,j$ entry of $A^{n-1}$ is equal to $1$; not every connected graph has a path of length $n-1$ between *every* two vertices. Also, you’re wrong about what it means for every entry of $(I+A)^{n-1}$ to be non-zero.

**Hint:** use the binomial expansion

$$

(I+A)^{n-1} = \sum_{k=0}^{n-1} \binom{n-1}k A^k

$$

- Puzzle with pirates
- Partial sums of $\sin(x)$
- How is the simplified version (below) of the Bromwich inverse Laplace transform integral derived?
- All naturals are T-finite, all finite sets are T-finite
- An identity of an Elliptical Integral
- Series of sequence with terms over series.
- For a polynomial $p(z)$ with real coefficients if $z$ is a solution then so is $\bar{z}$
- How, if at all, does pure mathematics benefit from $2^{74207281}-1$ being prime?
- Minimum eigenvalue and singular value of a square matrix
- Explanations of Lebesgue number lemma
- Showing that $2 \Gamma(a) \zeta(a) \left(1-\frac{1}{2^{a}} \right) = \int_{0}^{\infty}\left( \frac{x^{a-1}}{\sinh x} – x^{a-2} \right) \, dx$
- Ricci SCALAR curvature
- Reference Request to Prepare for Hatcher's “Algebraic Topology”
- Generating function of $a_{n}^2$ in terms of GF of $a_{n}$?
- How to show $(a^b)^c=a^{bc}$ for arbitrary cardinal numbers?