Prove a real block tridiagonal matrix is invertible 
Suppose matrix $A$ is a real block tridiagonal matrix where the blocks are all size $q \times q$ and the diagonal blocks $D_i$ are all invertible ($1 \leq i \leq n$). Furthermore, $A^t$ is block diagonally dominant.
(a) Prove $A$ is invertible.
(b) Prove $A$ has an $LU$ decomposition.

Not sure where to start. Thought I can decompose $A=D-L-U$ but got nothing. Tried to find the inverse of $A$ directly but it got really messy and we only know the diagonal entries $D_i$ are invertible.
 A: I will help you with part (a). For part (b) see the technical report "Block LU Factorization" by Demmel, Higham, and Schreiber.
Let $B = A^T$ and let $B_{i,j}$ denote the $(i,j)$ block of $B$. Then $B$ is strictly block diagonally dominant if
$$
(\|B_{i,i}^{-1}\|)^{-1} > \sum_{j\neq i} \|B_{i,j}\|~~\text{for all}~~i = 1,\ldots,n,
$$
where $\|\cdot\|$ is some induced matrix norm. Suppose there exists a nonzero vector $x\in\mathbb{R}^{nq}$ partitioned into blocks if size $q$ according to $x = (x_1,\ldots,x_n)^T$ such that $Bx = 0$. Without restricting generality suppose that $\|x\| = 1$. Clearly, there exists an index $i$ such that $0 < \|x_i\| = \max_{k=1,\ldots,n}\|x_k\|$. Thus
$$
B_{i,i}x_i = -\sum_{j\neq i} B_{i,j}x_j \implies \|x_i\| = \big\|B_{i,i}^{-1}\sum_{j\neq i} B_{i,j}x_j\big\| \leq \|B_{i,i}^{-1}\|\cdot\big\|\sum_{j\neq i}B_{i,j}x_j\big\|
$$
By the triangle inequality it follows that
$$
\|x_i\|(\|B_{i,i}^{-1}\|)^{-1} \leq \sum_{j\neq i} \|B_{i,j}\|\cdot\|x_j\| \implies (\|B_{i,i}^{-1}\|)^{-1} \leq \sum_{j\neq i} \|B_{i,j}\|\cdot\frac{\|x_j\|}{\|x_i\|}  
$$
Since $\|x_i\|$ is the maximum such norm we arrive at the contradiction that
$$
(\|B_{i,i}^{-1}\|)^{-1} \leq \sum_{j\neq i} \|B_{i,j}\|
$$
Therefore no such vector exists and consequently $B$ is invertible. Since $B = A^T$, $A$ is invertible.
