2

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$ ?

Bernard
  • 175,478
Ivan
  • 51
  • 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).

     – Ben Grossmann Apr 07 '19 at 07:29
  • 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. – Ben Grossmann Apr 07 '19 at 07:52

1 Answers1

2

$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.

Ben Grossmann
  • 225,327