Let $B$ be a $(n-1)×(n-1)$ matrix such that: all elements on diagonal equal $0$; and all other either $1$ or $\text{-}1$.

Let $A = \begin{bmatrix}B&(1,...,1)^T\\ (1,...,1)&1\end{bmatrix}$, so $A$ be a $n×n$ derived from $B$ by adding a row and column with $1$.

What could be the rank of the matrix $A$ ?

  • $\begingroup$ As established in this post, $B$ has a submatrix of rank at most $n-2$. Since this submatrix is in turn a submatrix of $A$, it follows that the rank of $A$ is $n-2$, $n-1$, or $n$. I suspect, however, that $A$ will generally be invertible (with odd determinant). $\endgroup$ – Omnomnomnom Apr 7 at 7:29
  • $\begingroup$ If we replace the bottom-right entry with a $0$, we get a matrix that, when taken modulo $2$, has eigenvalues $n-1$ with multiplicity $1$ and $-1$ with multiplicity $n-1$. I have not found a way to leverage this fact. $\endgroup$ – Omnomnomnom Apr 7 at 7:52

$A$ is necessarily of full rank, since its determinant is non-zero. We can show that the determinant is non-zero by showing that it is necessarily an odd number.

Following Hans's idea here, showing that $A$ always has odd determinant is equivalent to showing that the number of permutations on $n$ objects that either have no fixed point or fix only the final entry is odd. If $d_n$ denotes the number of derangements, then we wish to show that $d_n + d_{n-1}$ is necessarily odd.

We note that $d_n$ satisfies the recurrence relation $$ d_1 = 0, \quad d_n = n d_{n-1} + (-1)^n $$ so that $d_n$ is odd iff $d_{n-1}$ is even. It follows that $d_n + d_{n-1}$ is always the sum of an even and odd number, and is therefore odd.

  • $\begingroup$ $d_{n-1}$ corresponds to permutations with fixed one element, bottom right entry. And $d_{n}$ corresponds to permutations without fixed elements ? $\endgroup$ – Ivan Apr 7 at 11:22
  • 1
    $\begingroup$ Exactly ${}{}{}{}{}$ $\endgroup$ – Omnomnomnom Apr 7 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.