1
$\begingroup$

Lets say I have a $N \times N $ Hadamard matrix $A$ (I am referring to the Kronecker product construction of the Hadamard) and I would like to take the first $M$ rows out of it and then compute the Gramian matrix $G$ such that

$G = Ao \ 'Ao$

and $Ao$ is a $M \times N \ (M<<N)$ Hadamard matrix

I would like to know the relation between $M$ and the number of unique values $G$ might have. To explain the concept of unique values, lets consider an example.

If a $2 \times 2$ matrix of all ones is multiplied by another $2 \times 2$ matrix of all ones, we get a matrix containing $[2 \ \ 2; 2 \ \ 2]$, thus only one unique value : $2$.

If a Gramian matrix has less unique values, it can be used in an embedded system application as it is easier to store in memory as compared to a matrix which has a large number of unique values.

$\endgroup$
  • $\begingroup$ Can you clarify the question? By "$M\times N$ Hadamard matrix" do you mean a matrix with $M$ pairwise mutually orthogonal rows of length $N$, or do you mean an $M\times N$ submatrix of an $N\times N$ Hadamard matrix? (The set of matrix of the latter type is a subset of the set of matrices of the former type.) The values in $A$ in the case of Hadamard matrices are $-1$ and $1$. I'm not sure what "relation between number of unique values in $(G)$ and the values in $(A)$" would mean in this case. Also, I'm curious about the motivation for the question. $\endgroup$ – Will Orrick Jun 10 '15 at 14:01
  • $\begingroup$ by $M \times N$ Hadamard matrix I mean that I design a $N \times N$ Hadamard matrix where $N$ is a power of 2, and then I take the first $M$ rows of the matrix where $M<<N$. $\endgroup$ – azmuhak Jun 11 '15 at 8:37
  • $\begingroup$ The relation between between number of unique values in (G) and the values in (A) can be re stated as : Given a rectangular $M \times N where M << N$ matrix $A$, how can we find out the number of distinct/unique values in $A' \times A$, without actual multiplication and counting. $\endgroup$ – azmuhak Jun 11 '15 at 8:38
  • 1
    $\begingroup$ Some things to note about the Hadamard matrix case: the answer doesn't depend on $N$ (as long as $N\ge M$). The number of distinct values is $1$ when $M=1$; the number of distinct values is $2$ when $M=2^k$, $k\ge1$; it's $3$ when $m=2^k-1$, $k\ge2$; it's $4$ when $m=2^j(2^k-1)$, $j\ge1$, $k\ge2$ or when $m=2^k+1$, $k\ge2$; it's $5$ when $m=2^k-3$, $k\ge4$, when $m=2^k-7$, $k\ge5$, when $m=2^j(2^k+1)$, $j\ge2$, $k\ge2$, or when $m=2^j(2^k-1)+1$, $j\ge4$, $k\ge2$. $\endgroup$ – Will Orrick Jun 11 '15 at 14:35
  • 1
    $\begingroup$ The sequence that gives the number of distinct values when $m=1,2,3,\ldots$ is $1, 2, 3, 2, 4, 4, 3, 2, 4, 5, 6, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 4, 5, 6, 7, 4, 5, 4, 3, 2, 4, 5, 6, 5, 8, 7, 6, 5, 8, 9, 10, 7, \ldots$. This is not in OEIS. $\endgroup$ – Will Orrick Jun 11 '15 at 14:39
1
$\begingroup$

Let $H_1=\begin{bmatrix}1\end{bmatrix}$, $H_2=\begin{bmatrix}1 & 1\\ 1 & -1\end{bmatrix}$, and let $$ H_{2^{n+1}}=H_2\otimes H_{2^n}=\begin{bmatrix}H_{2^n} & H_{2^n}\\ H_{2^n} & -H_{2^n}\end{bmatrix}. $$ If $M=N=2^n$, then $G=H'_{2^n}H_{2^n}=2^nI$ and therefore $G$ has one distinct value, $1$, when $n=0$ and two distinct values, $0$ and $2^n$, when $n\ge1$.

Two observations about $H_{2^n}$: (1) its first row is all $1$s, (2) for $m\le n$, $H_{2^n}=H_{2^m}\otimes H_{2^{n-m}}$. Taken together, these observations imply that the first $2^m$ rows of $H_{2_n}$ look like $$ \begin{bmatrix}H_{2^m} & H_{2^m} & \ldots & H_{2^m}\end{bmatrix}, $$ where there are $2^{n-m}$ blocks in this matrix. Let $N=2^n$ and $M\le2^m$. The matrix $A_0$ with these dimensions consists of the first $M$ rows of the matrix above and therefore consists of the columns of the first $M$ rows of $H_{2^m}$, each repeated $2^{n-m}$ times. Since repeating columns does not affect the set of distinct elements in the Gram matrix $G=A_0'A_0$, the same set of distinct elements is obtained for every $n\ge m$. In other words, as long as $N\ge M$, the set of elements comprising the Gram matrix depends only on $M$, and not on $N$.

This immediately implies that if $M=2^m$, then there is one distinct value if $m=0$ ($N=1$), and there are two distinct values, $0$ and $2^m$, if $m\ge1$. Some other rules mentioned in my comment that can be readily proved:

  • if $M=2^m-1$, $m\ge2$, then there are three distinct values. This is proved by considering what happens when the last row is removed from the $2^m\times N$ matrix. If $m=0$, the result is the empty matrix, and there are no distinct values; if $m=1$, the result is the $1\times N$ matrix with all elements $1$, and there is one distinct value; if $m\ge2$ then the $2^m\times N$ matrix has the distinct values $2^m$ and $0$. The removed row contains both elements $1$ and elements $-1$. In the $(2^m-1)\times N$ matrix that is left, the product of two identical columns is $2^m-1\ge3$. The product of two distinct columns in which the removed elements are both $1$ or both $-1$ is less by $1$ than the product before the removal, which means it's $-1$. The product of two distinct columns in which the removed elements have opposite sign is greater by $1$ than the product before the removal, which means it's $1$. Hence there are three distinct values, $2^m-1$, $-1$, and $1$.
  • if $M=2^m+1$, $m\ge2$, then there are four distinct values. In this case the matrix has the form $$ \left[\begin{array}{cc|cc|c|cc}H_{2^m} & H_{2^m} & H_{2^m} & H_{2^m} & \ldots & H_{2^m} & H_{2^m}\\ j_{2^m} & -j_{2^m} & j_{2^m} & -j_{2^m} & \ldots & j_{2^m} & -j_{2^m}\end{array}\right], $$ where $j_k$ is the all-ones row vector of length $k$ and where the repeating pattern occurs $2^{n-m-1}$ times. The product of two identical columns is $2^m+1\ge5$; the product of two columns identical except for the last element is $2^m-1\ge3$; the product of two distinct columns with last element of the same sign is $1$; the product of two distinct columns with last element of opposite sign is $-1$.

The analysis for some of the other rules stated in my comment is similar but more involved. Also, some of the rules were not stated in the simplest possible way. In trying to reformulate the rules in a more concise way and to prove them, I stumbled on a recurrence that allows one to compute the number of distinct values for all $M$. This recurrence and its proof are below.

The recurrence: map $M$ to a word $w$ consisting of the letters $\bar{0}$, $1$, and $\bar{1}$ by the following procedure:

  1. write $M$ in base-$2$ as a string of $0$s and $1$s; the leading digit should be $1$;
  2. replace each string of one or more $0$s terminated on both ends by a $1$ or by the beginning or end of the string with $\bar{0}$;
  3. replace each string of two or more $1$s terminated on both ends by a $\bar{0}$ or by the beginning or end of the string with $\bar{1}$;
  4. leave each remaining $1$ as is.

Observe the adjacency conditions:

  • none of the three letters can ever be adjacent to another copy of the same letter;
  • $1$ and $\bar{1}$ can never be adjacent.

Examples:

  • $M=47=101111_2$ maps to $w=1\bar{0}\bar{1}$.
  • $M=101=1100101_2$ maps to $w=\bar{1}\bar{0}1\bar{0}1$.
  • $M=804=1100100100_2$ maps to $w=\bar{1}\bar{0}1\bar{0}1\bar{0}$.

Apply the following rules recursively to assign a score $s(w)$ to each word.

Initial conditions:

  • if $w=1$, then $s(w)=1$;
  • if $w=1\bar{0}1$, then $s(w)=4$.

Deflation rules:

  1. if $w=u\bar{0}$, where $u$ is a nonempty word, then $s(w)=s(u)+1$;
  2. if $w=v\bar{1}$, where $v$ is a possibly empty word, then $s(w)=s(v1)+2$;
  3. if $w=v\bar{1}\bar{0}1$, where $v$ is a possibly empty word, then $s(w)=s(v1)+4$;
  4. if $w=u1\bar{0}1$, where $u$ is a nonempty word, then $s(w)=s(u1)+4$.

The number of distinct values in the Gram matrix is equal to $s(w)$.

Examples:

  • for $m=47$, the score is $s(1\bar{0}\bar{1})=s(1\bar{0}1)+2=4+2=6;$
  • for $m=101$, the score is $s(\bar{1}\bar{0}1\bar{0}1)=s(\bar{1}\bar{0}1)+4=s(1)+8=1+8=9;$
  • for $m=804$, the score is $s(\bar{1}\bar{0}1\bar{0}1\bar{0})=s(\bar{1}\bar{0}1\bar{0}1)+1=s(\bar{1}\bar{0}1)+5=s(1)+9=10.$

Indeed, one can verify, by computing the Gram matrix of the first $47$ rows of the $64\times 64$ (or larger) Kronecker product Hadamard matrix, that there are six distinct values: $47$, $17$, $15$ $-15$, $1$, $-1$. Similarly, by computing the Gram matrix of the first $101$ rows of the $128\times 128$ (or larger) Kronecker product Hadamard matrix, one finds that there are nine distinct values: $101$, $27$, $-27$, $5$, $-5$, $3$, $-3$, $1$, $-1$. Finally, by computing the Gram matrix of the first $804$ rows of the $1024\times 1024$ (or larger) Kronecker product Hadamard matrix, one finds that there are ten distinct values: $804$, $220$, $-220$, $36$, $-36$, $28$, $-28$, $4$, $-4$, $0$.

Proof: We need to prove the initial conditions and the deflation rules. The initial conditions were proved above: $w=1$ corresponds to $N=1$ and $w=1\bar{0}1$ corresponds to $N=2^m+1$ with $m\ge2$.

Deflation rule 1: note that for $w$ to be well-formed, $u$ must end in $1$ or $\bar{1}$. Let $M$ be the matrix dimension corresponding to $u$; it must be odd. Let $g_1,g_2,\ldots,g_{s(u)}$ be the values in the Gram matrix of the $M\times N$ Hadamard matrix $A$. Since $M$ is odd, these values are all odd; in particular, none is $0$.

The matrix dimension corresponding to $w=u\bar{0}$ is $2^mM$ for some $m\ge1$. Let $B=A\otimes H_{2^m}$, which has dimensions $2^mM \times 2^mN$. As discussed above, the Gram matrix of $B$ has the same values as the Gram matrix of any Hadamard matrix of $2^mM$ rows. But the Gram matrix values of $H_{2^m}$ are $0$ and $2^m$, and so the Gram matrix values of $B$ are $$ 0,2^mg_1,2^mg_2,\ldots,2^mg_{s(u)}. $$ Hence $B$ has one more Gram matrix value than $A$.

Deflation rule 2: (Note: the proof I posted previously of deflation rule 2 made an assumption that does not hold for all words of the form $v\bar{1}$.) Let $M$ be a positive integer whose representation as a binary number is $de$, where $d$ is either empty or ends in $0$ and $e$ consists of $m\ge1$ $1$s. This implies that $M+1\equiv2^m\pmod{2^{m+1}}$. The proof proceeds by showing that if $m\ge2$, the Gram matrix of a matrix with $2M+1$ rows (which has binary representation $de1$) has the same number of distinct values as the Gram matrix of a matrix with $M$ rows, while if $m=1$, the Gram matrix of the matrix with $2M+1$ rows has two more distinct values than does that of the matrix with $M$ rows.

Let $H$ be a Kronecker product Hadamard matrix with a suitably large number $N$ of columns. The first $M+1$ rows of $H$ are of the form $B\otimes H_{2^m}$, where $B$ has an odd number of rows. Let $G_{M+1}$ be the Gram matrix of $B\otimes H_{2^m}$. Let $i,j\in\{1,2,\ldots,N\}$ be column indices. If $i\not\equiv j\pmod{2^m}$, then the product of the $i^\text{th}$ and $j^\text{th}$ columns of $B\otimes H_{2^m}$ is $0$; if $i\equiv j\pmod{2^m}$, then the product is an odd multiple of $2^m$.

Let $G_M$ be the Gram matrix of the first $M$ rows of $H$ and let its elements be $g_{ij}$. If $i\not\equiv j\pmod{2^m}$, then $g_{ij}=-1$ when the elements of row $M+1$ of $B\otimes H_{2^m}$ in columns $i$ and $j$ have the same sign and $g_{ij}=1$ when these elements have opposite sign. If $i\equiv j\pmod{2^m}$, then $g_{ij}\equiv2^m-1\pmod{2^{m+1}}$ when the elements of row $M+1$ of $B\otimes H_{2^m}$ in columns $i$ and $j$ have the same sign and $g_{ij}\equiv2^m+1\pmod{2^{m+1}}$ when these elements have opposite sign.

Consider the matrix of $2M+1$ rows obtained by deleting the last row of $B\otimes H_{2^{m+1}}$. Row $2M+1$ of this matrix is the Kronecker product of row $M+1$ of $B\otimes H_{2^m}$ and $\begin{bmatrix}1 & 1\end{bmatrix}$. Write column indices of this matrix as $2i+\delta$ and $2j+\epsilon$, where $\delta,\epsilon\in\{-1,0\}$ and $i$, $j$ are column indices of $B\otimes H_{2^m}$.

Now let $G_{2M+1}$ be the Gram matrix of the matrix in the previous paragraph. The $(2i+\delta,2j+\epsilon)$ element of $G_{2M+1}$ equals

  • $2g_{ij}+1$ if $\delta=\epsilon$ and the elements of row $M+1$ of $B\otimes H_{2^m}$ in columns $i$ and $j$ have the same sign.
  • $2g_{ij}-1$ if $\delta=\epsilon$ and the elements of row $M+1$ of $B\otimes H_{2^m}$ in columns $i$ and $j$ have opposite sign.
  • $1$ if $\delta\neq\epsilon$ and the elements of row $M+1$ of $B\otimes H_{2^m}$ in columns $i$ and $j$ have the same sign.
  • $-1$ if $\delta\neq\epsilon$ and the elements of row $M+1$ of $B\otimes H_{2^m}$ in columns $i$ and $j$ have opposite sign.

What can we conclude about the distinct values of $G_{2M+1}$? Among them are $1$ and $-1$ arising from the third and fourth items on this list, both of which occur for any $m\ge1$ since $M+1\ge2$ and therefore row $M+1$ of $B\otimes H_{2^m}$ contains both signs.

Also among the distinct elements of $G_{2M+1}$ are elements related to the distinct elements of $G_M$ according to the first two items on the list above. We consider two cases. (1) For each of the distinct $g_{ij}$ of $G_M$ that arises when $i\equiv j\pmod{m}$, we get an element $2g_{ij}+1\equiv2^{m+1}-1\pmod{2^{m+2}}$ of $G_{2M+1}$ when the elements of row $M+1$ of $B\otimes H_{2^m}$ in columns $i$ and $j$ have the same sign, or $2g_{ij}-1\equiv2^{m+1}+1\pmod{2^{m+2}}$ when the elements of row $M+1$ of $B\otimes H_{2^m}$ in columns $i$ and $j$ have opposite sign. The elements of $G_{2M+1}$ that arise in this way from distinct elements of $G_M$ are distinct. They are also distinct from $-1$ and $1$. (2) For $g_{ij}=\pm1$ that arise from the situation where $i\not\equiv j\pmod{2^m}$, we get $2g_{ij}=2(-1)+1=-1$ when the elements of row $M+1$ of $B\otimes H_{2^m}$ in columns $i$ and $j$ have the same sign and $2g_{ij}=2(1)-1=1$ when the elements of row $M+1$ of $B\otimes H_{2^m}$ in columns $i$ and $j$ have opposite sign.

In conclusion, for $m\ge2$, the third and fourth items on the list above ($\delta\ne\epsilon$) guarantee Gram matrix elements $-1$ and $1$. The first and second items give a one-to-one correspondence between $\delta=\epsilon$, $i\equiv j\pmod{2^m}$ elements of $G_{2M+1}$ and $i\equiv j\pmod{2^m}$ elements of $G_M$. For $m\ge2$ these elements never include $\pm1$. The only remaining case is $\delta=\epsilon$, $i\not\equiv j\pmod{2^m}$, which only produces elements $\pm1$, already guaranteed by the $\delta\ne\epsilon$ case. This establishes that the number of distinct Gram matrix elements is the same for any $m\ge2$.

It remains to prove that the number of distinct Gram matrix elements for $m=2$ is two more than the number for $m=1$. Suppose that for $m=1$ there are $k$ distinct values of $G_M$ of the $i\equiv j\pmod{2m}$ type. These map to $k$ distinct values of $G_{2M+1}$ of the $\delta=\epsilon$, $i\equiv j\pmod{2m}$ type, none of which equals $\pm1$. So $G_{2M+1}$ has $k+2$ distinct elements. We need to show that $G_M$ contains no elements distinct from the $k$ already identified. The only other values of $G_M$ are of the $i\not\equiv j\pmod{2m}$ type, which must equal $\pm1$. Therefore we need to show that if $G_M$ contains a $1$ of the $i\not\equiv j\pmod{2^m}$ type, then it also contains a $1$ of the $i\equiv j\pmod{2^m}$ type, and likewise for $-1$. Since $2^m=2^1=2$, this amounts to showing that if the set of elements of $G_M$ arising from one column of odd index and one column of even index includes $1$, then so does the set of element arising from two columns of odd index or two columns of even index.

In this case $G_M$ is the Gram matrix of the matrix—call it $C$—obtained by deleting the last row of $B\otimes H_2$, where $B$ contains an odd number of rows. If $B$ consists of a single row, then all elements of $G_M$ equal $1$, and the statement holds. Otherwise the last row of $B$ contains elements of both signs which means that the deleted row of $B\otimes H_2$ includes odd numbered columns containing $1$ and odd numbered columns containing $-1$ and likewise for even numbered columns. So there are elements of $G_M$ corresponding to odd/even or even/odd pairs of column indices of both signs. On the other hand, when $m=1$, $M-1$ is a multiple of $4$, which we can assume to be a positive multiple of $4$ since the case where $B$ has a single row has already been dealt with. But the first $M-1$ rows of $C$ are then of the form $D\otimes H_4$, so that columns whose indices are not equivalent mod $4$ have product $0$. Row $M$ of $C$ is of the form $f\otimes\begin{bmatrix}1 & 1 & 1 & 1\end{bmatrix}$, where $f$ is a vector containing both $-1$ and $1$. So there is a pair of columns of $C$ of, say, even index, one equivalent to $0$, the other equivalent to $2\pmod{4}$ whose product is $1$ and another such pair whose product is $-1$. (Note: although not needed here, the same result holds when $M+1$ is a multiple of $4$, by a similar argument.)

Deflation rule 3: (Sketch of proof.) The proof is a modification of the proof of deflation rule 2. Instead of applying the transformation $M\rightarrow2M+1$ repeatedly, we change the transformation in the last step to $M\rightarrow2^rM+1$, where $r$ is the length of the string of bits corresponding to the letters $\bar{0}1$ in the word. Instead of column indexing $2i+\delta$, $2j+\epsilon$ with $\delta,\epsilon\in\{-1,0\}$, we have column indexing $2^ri+\delta$, $2^rj+\epsilon$ where $\delta,\epsilon\in\{0,-1,-2,\ldots,1-2^r\}$. The $\delta\ne\epsilon$ case is the same, leading to Gram matrix elements $-1$ and $1$. The $\delta=\epsilon$ case again breaks into the $i\equiv j\pmod{2^m}$ and $i\not\equiv j\pmod{2^m}$ cases. In the former there is again a one-to-one correspondence between the associated Gram matrix elements of $G_M$ and those of $G_{2^rM+1}$. In the latter, instead of $-1\mapsto2(-1)+1=-1$ we have $-1\mapsto2^r(-1)+1$, and instead of $1\mapsto2(1)-1=1$ we have $1\mapsto2^r(1)-1$. Since these elements are not equal to $\pm1$, instead of having two more Gram matrix elements than in the $m=1$ case, we have four more.

Deflation rule 4: (Sketch of proof.) The proof is essentially that of deflation rule 3. The only difference is that the $M\rightarrow2^rM+1$ transformation is applied immediately to the $m=1$ case, without the $M\rightarrow2M+1$ transformation ever being applied. Again we get Gram matrix elements $-1$ and $1$ from the $\delta\ne\epsilon$ case and a one-to-one correspondence between the $\delta=\epsilon$, $i\equiv j\pmod{2^m}$ Gram matrix elements of $G_{2^rM+1}$ and the $i\equiv j\pmod{2^m}$ elements of $G_M$. Again if $G_M$ contains both $-1$ and $1$, then these map to elements $2^r(-1)+1$ and $2^r(1)-1$, which are distinct from all the rest, giving a total of four more distinct Gram matrix elements in $G_{2^rM+1}$ than in $G_M$. The only special case is when $G_M$ does not contain both $-1$ and $1$. As discussed in the proof of deflation rule 2, this only occurs when $B$ has a single row and $m=1$, which means that $M=1$ and all Gram matrix elements equal $1$. In this case $G_{2^rM+1}$ contains only three more elements than $G_m$, which is the reason that deflation rule 4 only applies when $u$ is nonempty. The initial condition $s(1\bar{0}1)=4$ handles the case where $u$ is empty.

Nonrecursive formula: define $$ \begin{aligned} a(w)&=\begin{cases}0 & \text{last letter of $w$ is $\bar{0}$,}\\ -1 & \text{last letter of $w$ is not $\bar{0}$,}\end{cases}\\ b(w)&=\begin{cases}1 & \text{first letter of $w$ is $\bar{1}$,}\\ 0 & \text{first letter of $w$ is $1$,}\end{cases}\\ c(w)&=\begin{cases}-1 & \text{last non-$\bar{0}$ letter of $w$ is $\bar{1}$,}\\ -3 & \text{last non-$\bar{0}$ letter of $w$ is $1$.}\end{cases} \end{aligned} $$ Then $$ s(w)=\begin{cases} 1 & \text{if $w=1$,}\\ 2 & \text{if $w=1\bar{0}$,}\\ 4\left\lfloor\frac{\lvert w\rvert+1}{2}\right\rfloor+a(w)+b(w)+c(w) & \text{otherwise.} \end{cases} $$

Proof: The cases $w=1$, $w=1\bar{0}$ follow immediately from the recurrence. Otherwise, we may assume that $w$ ends with $\bar{0}$. If it doesn't, we append $\bar{0}$ to $w$ and adjust the score at the end by subtracting $1$. This accounts for the $a(w)$ term. Now by assumption, $w$ is obtained by stringing together the units $1\bar{0}$ and $\bar{1}\bar{0}$. The factor $\left\lfloor\frac{\lvert w\rvert+1}{2}\right\rfloor$ is the number of units. So, apart from the adjustment $a(w)$ already explained, the score is the number of units times $4$ plus adjustments that depend on whether the first unit is $1\bar{0}$ or $\bar{1}\bar{0}$ and whether the last unit is $1\bar{0}$ or $\bar{1}\bar{0}$.

We prove this by induction on the number of units. One easily checks that the formula gives the correct score for the word $\bar{1}\bar{0}$ and all words of two units: $\bar{1}\bar{0}\bar{1}\bar{0}$, $\bar{1}\bar{0}1\bar{0}$, $1\bar{0}\bar{1}\bar{0}$, and $1\bar{0}1\bar{0}$. Now suppose that the formula holds for all words of $k\ge2$ units. Then a word of $k+1$ units is either $w\bar{1}\bar{0}$ or $w1\bar{0}$, where $w$ is a word of $k$ units.

If $w=v\bar{1}\bar{0}$, then $$ s(w\bar{1}\bar{0})=s(v\bar{1}\bar{0}\bar{1}\bar{0})=s(v1)+7=s(v\bar{1})+5=s(v\bar{1}\bar{0})+4=s(w)+4, $$ which agrees with the formula since $w\bar{1}\bar{0}$ and $w$ have the same adjustment terms. Likewise $$ s(w1\bar{0})=s(v\bar{1}\bar{0}1\bar{0})=s(v1)+5=s(v\bar{1})+3=s(v\bar{1}\bar{0})+2=s(w)+2, $$ which agrees with the formula since $c(w\bar{1}\bar{0})=-3$ while $c(w)=-1$.

Now suppose $w=v1\bar{0}$. Since $k\ge2$, $v$ is nonempty. Therefore $$ s(w\bar{1}\bar{0})=s(v1\bar{0}\bar{1}\bar{0})=s(v1)+7=s(v1\bar{0})+6=s(w)+6, $$ which agrees with the formula since $c(w\bar{1}\bar{0})=-1$ while $c(w)=-3$. Likewise $$ s(w1\bar{0})=s(v1\bar{0}1\bar{0})=s(v1)+5=s(v1\bar{0})+4=s(w)+4, $$ which agrees with the formula since $w1\bar{0}$ and $w$ have the same adjustment terms.

$\endgroup$

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.