I think I am confused with the following concept. It appears in the book by Watkins, "Fundamentals of matrix computations", p57:
The envelope of a symmetric or upper-triangular matrix $A$ is a set of of ordered pairs $(i,j)$, $i<j$, representing the element locations in the upper triangule of $A$, defined as follows: $(i,j)$ is in the envelope of $A$ if and only if $a_{kj}\neq 0$ for some $k\leq i$. Thus if the first nonzero entry of the $j$th column is $a_{mj}$ and $m<j$, then $(m,j),(m+1,j),\dots,(j-1,j)$ are the members of the envelope of $A$ from the $j$th column.
If I have a triangular matrix $T$, I understand from the definition that the envelope would be the second upper-diagonal of $T$. What confuses me is the part that follows the Thus. Is my interpretation correct?
(I'll use $*$ for nonzero elements to make it clearer.) Consider: $$A=\left(\begin{matrix} * & 0 & 0 \\ 0 & * & * \\ 0 & * & 0 \\ \end{matrix}\right)$$ and $$B=\left(\begin{matrix} 0 & 0 & * & 0 \\ 0 & 0 & 0 & * \\ 0 & 0 & 0 & * \\ 0 & 0 & 0 & 0\\ \end{matrix}\right)$$ (B is strictly upper triangular).
The envelope of $A$ is a subset of $\{(1,2),(1,3),(2,3)\}$.
Is $(1,2)$ in the envelope of $A$? That is, is $a_{k,2}\neq 0$ for some $k\le 1$? Or to make it simple, is $a_{1,2}\neq0$? As it is not, $(1,2)$ is not in the envelope of $A$.
Is $(1,3)$ in the envelope of $A$? Or, as before, is $a_{1,3}\neq0$. It is zero, so $(1,3)$ is not in the envelope either.
Is $(2,3)$ in the envelope? By definition this is: is $a_{k,2}\neq 0$ for some $k\le 2$? Equivalently: is $a_{1,3}\neq 0$ or $a_{2,3}\neq 0$. The first option has already been discarded, but $a_{2,3}\neq0$ so $(2,3)$ is in the envelope.
If you want a matrix representation of this we could say that the envelope of $A$ is $$A=\left(\begin{matrix} \cdot & 0 & 0 \\ \cdot & \cdot & 1 \\ \cdot & \cdot & \cdot \\ \end{matrix}\right)$$ where the dots mean that the corresponding pair is out of consideration by the definition of envelope. You just take the triangle above the diagonal, and for each position you put a zero if you have zero there and at all the positions above that one, and you put a one (that is, it belongs to the envelope) if you have a nonzero element at that position or above.
This shows that to calculate the envelope, nothing on the lower triangle including the diagonal is relevant, so the envelope of any matrix is equal to the envelope of the strictly upper triangular matrix you get when you set to $0$ all the elements of positions $(i,j)$ with $i\ge j$.
Now $B$ is such a matrix. It's envelope is
$$B=\left(\begin{matrix} \cdot & 0 & 1 & 0 \\ \cdot & \cdot & 1 & 1 \\ \cdot & \cdot & \cdot & 1 \\ \cdot & \cdot & \cdot & \cdot \\ \end{matrix}\right).$$
I hope it makes it more clear.