A is a matrix of integers , prove that A+I is invertible Question:
$2 \le d \in \Bbb Z$
Let $A \in M_n(\Bbb Q) s.t$ All of it's elements are integers divisible by d.
Prove that $I+A$ is invertible.
What I thought:
I thought of using the determinant of A and extracting $d^2$ from it, but I can't use that on det(A+I)... tried also to calculate the determinant for n=2, and got a polynomial of 2nd degree (With no idea on how to prove that it doesn't equal 0).
 A: Hint: Can $-1$ be an eigenvalue for $A$?
Alternatively: What is the determinant of $A+I$ modulo $d$?
A: There's no need of doing an induction; when you consider your matrix $I+A$ modulo $d$ it's just the identity, so
$$
\det(I+A)\equiv 1\pmod{d}
$$
and it can't be $0$.
Let's do it with more details. Your matrices are in $\def\Z{\mathbb{Z}}M_n(\Z)$. We have a ring homomorphism $\delta\colon\Z\to\Z/d\Z$ that easily extends to a homomorphism $\delta_n\colon M_n(\Z)\to M_n(\Z/d\Z)$, applying $\delta$ to each entry of the matrix.
What can we say about $\delta(\det A)$ and $\det(\delta_n(A))$? They are equal for any matrix $A$:
$$
\det A=\sum_{\sigma}(-1)^{\mathrm{sgn}(\sigma)}
  a_{1,\sigma(1)}a_{2,\sigma(2)}\dots a_{n,\sigma(n)}
$$
so applying $\delta$ to it is exactly the same as doing
$$
\sum_{\sigma}(-1)^{\mathrm{sgn}(\sigma)}
  \delta(a_{1,\sigma(1)})\delta(a_{2,\sigma(2)})\dots \delta(a_{n,\sigma(n)})
$$
($\sigma$ runs over the permutations of $\{1,2,\dots,n\}$).
If now the matrix $A$ has all of its entries in $d\Z$, $\delta_n(A)=0$ (the null matrix in $M_n(\Z/n\Z)$); thus
$$
\delta(\det(I+A))=
\det(\delta_n(I+A))=
\det I=1
$$
(the unity in $\Z/dZ$), which means exactly
$$
\det(I+A)\equiv 1\pmod{d}
$$
Thus $\det(I+A)\ne0$, so the matrix is invertible in $M_n(\mathbb(Q)$.
A: Look at the laplace expansion of the determinant of $A+I$ (http://en.wikipedia.org/wiki/Laplace_expansion)
Your matrix has the form $$
  A = d\left(
  \begin{matrix}
    k_{1,1} &\ldots &k_{1,n} \\
    \vdots  &\ddots &\vdots \\
    k_{n,1} &\ldots &k_{n,n}
  \end{matrix}\right)
$$
and by laplace expanding the determinant using the first row you get $$
  \det(A+I) = (dk_{1,1} + 1)C_{1,1} + dk_{1,2}C_{1,2} + \ldots
$$
Note that $C_{1,1} = \det(A_1 + I)$ where $$
  A_1 = d\left(
  \begin{matrix}
    k_{2,2} &\ldots &k_{2,n} \\
    \vdots  &\ddots &\vdots \\
    k_{n,2} &\ldots &k_{n,n}
  \end{matrix}\right) \text{.}
$$
Edit:: (I previously suggested to decude from $\det(A+I)=0$ that $C_{1,1}$ is zero, but that's not as obvious as I initially thought, since you only get "zero or a multiple of $d$". You'd need an extra induction step to show that the multiple of $d$ case doesn't happen. One can avoid that by looking at everything modulo $d$)
From the above, you get by induction that  $$
  \det(A+I) \equiv C_{1,1} \equiv \det(A_1+I) \equiv \ldots \equiv \det(A_{n-1}+I) \equiv 1\mod d \text{.}
$$
