NATIONAL BUREAU OF STANDARDS REPORT

2k92

ON CERTAIN CHARACTER MATRICES

^5 £ L*

by

D. H. Lehmer

National Bureau of Standards, Los Angelesj, California

NBS

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS

/
U. S. DEPARTMENT OF COMMERCE

Diaries Sawyer, Secretary

NATIONAL BUREAU OF STANDARDS

A. V. As tin, Acting Director

THE NATIONAL BUREAU OF STANDARDS

The scope of activities of the National Bureau of Standards is suggested in the following listing of the divisions and sections engaged in technical work. In general, each section is en- gaged in specialised research, development, and engineering in the field indicated by its

title. A brief description of the activities, and of the resultant reports and publications,

appears on the inside of the back cover of this report.

1. ELECTRICITY. Resistance Measurements. Inductance and Capacitance. Electrical Instruments. Magnetic Measurements. Electrochemistry.

2. OPTICS AND METROLOGY. Photometry and Colorimetry. Optical Instruments. Photographic

Technology. Length. Gage.

3- HEAT AND POWER. Temperature Measurements. Thermodynamics. Cryogenics. Engines and

fabrication. Engine Fuels.

4. ATOMIC AND RADIATION PHYSICS. Spectroscopy. Radiometry. Mass Spectrometry, physical Electronics. Electron Physics. Atomic Physics. Neutron Measurements. Nuclear Physics. Radioactivity. X-Rays. Betatron. Nucleonic Instrumentation. Radiological Equipment. Atomic Energy Commission Instruments Branch.

5. CHEMISTRY. Organic Coatings. Surface Chemistry. Organic Chemistry. Analytical Chemistry. Inorganic Chemistry. Electrodeposition. Gas Chemistry. Physical Chemistry. Thermochemistry. Spectrochemistry. Pure Substances.

6. MECHANICS. Sound. Mechanical Instruments. Aerodynamics. Engineering Mechanics. Hydraulics. Mass. 'Capacity, Density, and Fluid Meters.

7. ORGANIC AND FIBROUS MATERIALS. Rubber . Textiles. Paper. Leather. Testing and

Specifications. Organic Plastics. Dental Research.

8. METALLURGY. Thermal Metallurgy. Chemical Metallurgy. Mechanical Metallurgy . Corrosion.

9. MINERAL PRODUCTS* Porcelain and Pottery. Glass. Refractories. Enameled Metals. Building Stone. Concreting Materials. Constitution and Microstructure. Chemistry ' of Mineral

Products.

10. 8UILDING TECHNOLOGY. Structural Engineering. Fire Protection. Heating and Air Conditioning. Exterior and Interior Coverings. Codes and Specifications.

II* APPLIED MATHEMATICS. Numerical Analysis. Confutation. Statistical Engineering. Ma- chine Development.

12* ELECTRONICS. Engineering Electronics. Electron Thbes. Electronic Computers. Electronic Instrumentation.

13. ORDNANCE DEVELOPMENT. Mechanical Research and Development. Electromechanical

Fuzes. Technical Services. Missile Fuzing Research. Missile Fuzing Development. Projectile Fuzes. Ordnance Coofonents. Ordnance Teats. Ordnance Research.

14. RADIO PROPAGATION. Upper Atmosphere Research. Ionospheric Research. Regular Propagation Services. Frequency Utilization Research. Tropospheric Propagation Research. High

Frequency Standards. Microwave Standards.

15. MISSILE DEVELOPMENT. Missile Engineering. Missile Dynamics. Missile Intelligence.

Missile Instrumentation. Technical Services. Combustion.
NBS PROJECT

1101-11-5100

Februaiy lU, 1952

NBS REPORT

1U92

ON CERTAIN CHARACTER MATRICES*

by

D. H* Lehxner

National Bureau of Standards, Los Angeles £ California

PREPRINT

The preparation of this paper was sponsored (in part) by the

Office of Naval Research

This report is issued i in say form, either in i fro* the Office of the I

Approved for public release by the

Director of the National Institute of

Standards and Technology (NIST) on October 9, 2015

», reprinting, or reproduction

•mission in writing is obtained

kshington 25, D- C.
. ?

...
MBS Hot lb92

2-lii-52

PREPRINT

On Certain Character Matrices'""

by

D. H. Lehmer

National Bureau of Standards, Los Angeles, California

For only a very limited class of matrices M is it possible to give

explicit formulas for the determinant of M, the general element of i-A,

the characteristic roots of M and the inverse of M* Non-trivial instances

of such matrices are useful as examples in testing the correctness and

efficacy of various matrix computing routines especially -when the elements of the matrices are exact integers or rational numbers. The purpose of this note is to indicate a new set of such matrices* Although

they arose in connection with a class of exponential sums, they appear*

to warrant an independent treatment. A discussion of the most general

case will not be attempted here. The matrices considered are real and

symmetric and of order p-1 where p is an odd prime.

The elements of our matrices are equal to Ch 1 or -1 and are based

on what are called real non-principal characters modulo p # r These

are^ for the cases considered, Legendre* s symbols for which we use the

if p divides a

p if the congruence x = a (mod p) is

impossible

otherwise

The preparation of this paper was sponsored (in part) by the

Office of Naval Research.

notation [1]

W- <§> s

<

o

-i

+i
.

.
2

For example if p = 7 we have

-X(a)

0 1 2 3 U 5 6

o l l-l l-l-l

Besides the simple properties

X^ a) X(b ) " X(ab ) X(a + p) - X( a)

we use the following identities

(1)

(2)

P"1

E x^ a + k) = ~

E 'X^ a + k^ X(b+k) “ P S& - 1 “ X(a) X(h)

where is Kronecker 1 s delta modulo p^ that is

1 a = b (mod p)

0 a ^ b (mod p)

The first of these identities is equivalent to the well known fact

that there is a residue for every noi>-residue modulo p. The second

identity may be written

P

-1 b

£ x( a+k) 'X(b * k)

*= p ya

D - 1 • k-o

2 This is obvious if a § b (mod p) since \“(a+k) = 0 or 1 according as a + k is divisible by p or not. If a d b (mod p) we may
i a I •
3

set b - a e r (mod p) and write the left side as follows

*Z ^(a+k) 'XCb+k) • £ X( h) X(r+h) • k«so h**o

If x^e denote this sum by S(r) and x-rrite

him (mod p)

xre have

p-i

S(r) “ Z )c( m) X(rm + r)

mesO

= >

2

( r) Z *X(m) XCl+m) *= S(l) # ra«o

Hence to show that S(r) = -1 we have only to show that

Vz1

Z S(r) • 1 - p * r=l

How

p-l p-l p-l

Z S(r) - Z z X(h) ^(r+ h)

r=l r»l h*0

P-l P-l

* z Xh) z >(r+ h)

hco r=l

P-l ? - - Z V ( h) - - (p-D

hso

by (l). This proves (2) in all cases. This identity appears to

be due to E. Jacobsthal [2].
. ' _ I
h

With these preliminaries we proceed to introduce our general

matrix and to give its properties.

Let t< be any integer parameter and let M* be the square

matrix of order p~l whose general element a^. is XC^ + i+j),

then;

I. The inverse has for its general element

- jxC* +i + 3) - X(* +i) ~ X<* +3) + X(*)J /p •

II o The characteristic equation

1 X X - | - 0

E=3

of is ( X

2 - Pr ( x

2 + XW)A-1) = 0 .

IIIo The determinant of is - (-p) (P”"3)/2

^ The result III follows at once from II by setting X ~ 0. The

result Ij once guessed^ may be verified as follows* We have to

show that

A ^

a

Substituting^ we have

-1 p-*1 c 1

p z x^ +±+k) i x(* +k+j) - x(* +k) - xw+d) + xo*)r

k^l L

* p^tp £ i^-l-X(* + i) X(°< + d) - P f^+i + 1+ X(°<+ XM

>(* + d ) - >(*o| (- X^ + i) ) ]

by (l) and (2), Since i ^ 0 (mod p) the above expression reduces

as required.
4

.
It remains to prove II, The method of proof given below is

not the most direct one that could be given,”** It has the merit,

however, of producing as a byproduct the general element of any

power of and this information may be useful in checking routine

computations of powers of a given matrix.

If we denote by a.^ the general element of we have

piy1' = XU +i+j) - M* + i) “ XU + o) + XU)

a

(°) p 5

ij h

a

ij

1'

1 = XU + i+ j)

p - XU+ i) XU + j) - 1

the last result following directly from (2)

An inspection of even

(k) this small sample of a.. together with considerations of symmetry

“d

(k) leads one to the conclusion that a^ depends somewhat on the

parity of k and that in making an inductive proof of the general

(k) form of a.. one should assume that

(3) a

ij^ * %(ij3) + s

v[ X(* + i) + XU + 5)] + pv XU+ i) X(« + j)+Ck

where depend on ©< and p only and

yk

(i»j) - -

p^/2

^

j if k is even

(k“l)/2

+ if k is odd

"*"An alternative short method of proof was suggested by R„ M, Robinson
.

-

m • i

.
6

At least* ( 3 ) is seen to hold for k = —1, 0, 1* 2 and we have in

fact

S e 0

0

T)O

81 0 c «= 0

0

(It) S-^ s 0 p

x

s 0

IQ H

O 0

• u 0 CM CO P

2

-1 ^2

” -1

That a.^ has the form ( 3 ) follows at once from (l) and (2) and*

moreover* these latter identities give us recurrence relations for

the P^. and C

y

0 In fact if we assume that (3) holds for k = 2m

and if we substitute into the relation

L (2m+l) c

Pg1 ^ A

a.ira

(2»>

ro

we find

S

2m+1

= " P

2m

= " ^ ^^ S2m " C 2m

P2m+1

s " S

2m “ P2m

"

C 2m+1

e " S

2m *

Similarly we find

( 6 )

S

2m+2

* " 'M*') S

2m+i

“ C 2m+1

“ " P2m+1

P

2k+2 “ " p D

2m+1 " P2m+1

r m c 0 2m+2

= “ P “ b 2m+l *

We have only to solve these difference equations for S^* P^*

subject to the initial condition ( 4)0
•
7

The case of X( *0 s 0 is much simpler than XC* ) s + 1* In

fact the above relations then become simply

“ Sk+1 “ Ck

= Pk

C 2m+1

" C 2m-1

'2m

m n - p + C 2m *

The solution is easily seen to be

0 P2m

“ C2m

e X) ^~ X)

S~ ' “ (P

m-DAP-1) P2m+1

e

^2m+l

" 0

2m

5 2m+l

Hence if

a

±j

c X(i + 5)

then

(7) a.<

(8) a

(2m+l)

ij

{»*!)* 4

m - m -v / . p -1

P Xu + o) + ^“TT 1 \(i)+ >(j)

In case *(«) ^ 0 the solution of the systems (5) and (6)

involves the Fibonacci numbers

U

n

- (A

n

- B

n)/(A— B)

'

where

A - | (1 + /?) , B - f (1 -vT) .
! -
8

Early values of U

n

are given by the following table

n

U

n

-2-10123U56 7 8

-1 1 0 1 1 2 3 5 8 13 21

and in general

U . « U + U . . n+1 n n-1

In what follows we shall need to refer also to the companion sequence

( 9 ) V «=A

n +Bn =U , + U - n n+1 i>-l

The solution of ( 5 ) and (6) may be given as follows

S, e — p _ k k-1

m+1

2m+l X(^) Ip -P U2m+2

+U2m /(p'“ 3p+1)

( 10 ) C

2m+1 “ X<«> 1

pffi " p U

2m

+ U2m-2 \ /&-*+ *>

P- “ "

-i pm+1 -

pm "P U

2m+l +U21>-ll‘ /(P

2

2m -3P + D

(H)

G2m^iPra+1" 2P

m

”P U2^1 +U2^3

2

V(v -3p + l)

The fact that these values satisfy the difference equations (5),

(6) and the initial conditions (Ij.) may be verified without using

anything more complicated than the fact that

U - 3U o ~ 1 ! • n n~2 nr-4

Of course the expressions (10) and (11) are polynomials in p®
I ' I $J p * 8
9

If (10) and (11) are substituted into (3) we obtain expressions for a.!^ and a

(2m+l)

3-3 13

For example

( 12 )a^^ s *)c(^ + i+j) + (p+2) j^( ©< + i) + 'XC <K J

) J* + (p + 3) X(*) )c(^ + i) X(®< + 3) + •

We note that this does not become- (8), with m = 2 S if we set = 0,

which

is also the sum of the k-th powers of the characteristic roots of

The case of )((^) * 0 is simple. From (7) and (8) we have

We now consider the trace of m*35 that is the sum 2?*?" a.^

3

s3! 33

P

Y

1

a,<

2m)

A

(p-1) P

m - 2(p

lu -l) = (p-3) p

1 ' 1 + 2m m

P

y

X

a (2m+l) = 0

Hence in both cases

2 -if

1 • ¥ « *

{

_ ,k _k

•p*0 * (-±) + 1

Since this holds for k = 1, 2 3 3* ••• the characteristic roots of

M0 must be those of the equation

( 13 ) (X

2 -p) (p-3 )/2 (X2 -l) 0 .

This proves II in case \{*<) 88 0*

For x(-o * o we find from (3)

P"X

„ (2m)

- (p-1) p

m - 2 X(a) S_ + (p- 2) P„ + (p- 1) C

33 2m 2m '2m

f a

j

2m+1) - - X(a)pm

- 2 X(a)S2m+1 + (P“2)P2m+1 + (p-DC^ . 3 *0,
1 tl .
10

If we substitute from (10) and (ll) and simplify we obtain

w2m)

0=1

(p - 3)p

m

+ + U

2m+]_

(p-3)p

m

+

a

(2m+l) „ A 33 *(•0^2 + V

\ ( ^ ) ^2n+l •

Recalling the definition (9) of we may write in general

f = |(p-3)(ph

k

+ |(p-3)(-ph

k

+ (-}(«)A)

k

+ (- X(«)B)

k

. 0=1

This shows lithat the characteristic roots of consist of J(p=3)

roots p

2

, J(p— 3) roots -p2

, - ^(«<)A and - ")((^0B o Since

A + B *® 1 , A B e «l 9

the characteristic equation of is

(\2

-p) (i^3)/2 U

2

+ *(*)X-i) = 0 .

Although this was derived on the assumption that *(®0 / o s if

we set X<*0 - 0 we do obtain (l3)o This completes the proof

of II.

Concerning the latent vectors of M the reader may verily

that, corresponding to a root

f> of

\(^) A - i ® o
1

'

.
XL

there is the latent vector whose j—th component is

x(* + o) - y(.*) - f •

The following example will illustrate the foregoing* We take

p a 7 5 ® 3 , then our matrix It, is

"3

by 7 we obtain

-1 -1 0 1 1 -1

=1 0 1 1 -1 1

0 i 1 -1 1 -1

1 i -1 1 -1 -1

1 -i 1 -1 -1 G

-1 i -1 =1 0 1

-U9* if the elements of M~'

-U —2 m1 —1 -2 -u

-2 1 2 1 *•2 0

-1 2 2 -1 0 -2

*=1 1 -1 0 -3 “3

-2 -2 0 -3 •"It -3

-U 0 —2 -3 -3 ~2

BF (12) we have j for example9

5L5

-U2 -Uo 9 57 56 «ia

-Uo -29 20 39 —IjO 58

9 20 20 -59 58 -Uo

57 39 -59 H8 -la -ia

56 -IjG 58 -la -U2 7

-U2 58 -Uo -la 7 56

Februaiy 26 5 1952
‘

'
12

References

[1] See for example E. Landau, Elementare Zahlentheorie

'New York, Chelsea, I9I4.6 , p* 83-87*

[2] E. Jacobstahl, u fjber die Darstellung der Primzahlen der Form

Un + 1 als Summe zweier Quadrate,” Jour. ftCr. Math. v. 132 a 1907, pp. 238-2U5.
.
THE NATIONAL BUREAU OF STANDARDS

Functions and Activities

The National Bureau of Standards is the principal agency of

the Federal Government for fundamental and applied research in physics, mathematics, chemistry, and engineering. Its activities range

from the determination of physical constants and properties of materials, the development and maintenance of the national standards

of measurement in the physical sciences, and the development of

methods and instruments of measurement, to the development of special

devices for the military and civilian agencies of the Government.

The work includes basic and applied research, development, engineering, instrumentation, testing, evaluation, calibration services,

and various scientific and technical advisory services.. A major

portion of the NBS work is performed for other government agencies,

particularly the Department of Defense and the Atomic Energy Commission. The functions of the National Bureau of Standards are set

forth in the Act of Congress, March 3, 1901, as amended by Congress

in Public Law 619, 1950. The scope of activities is suggested in

the listing of divisions and sections on the inside of the front

cover.

Reports and Publications

The results of the Bureau’s work take the form of either actual

equipment and devices or published papers and reports. Reports are

issued to the sponsoring agency of a particular project or program.

Published papers appear either in the Bureau’ s own series of publications or in the journals of professional and scientific societies.

The Bureau itself publishes three monthly periodicals, available

from the Government Printing Office : the Journal of Research, which

presents complete papers reporting technical investigations; the

Technical News Bulletin, which presents summary and preliminary re- ports on work in progress; and Basic Radio Propagation Predictions,

which provides data for determining the best frequencies to use for

radio communications throughout the world. There are also five

series of nonperiodical publications: the Applied Mathematics Series, Circulars, Handbooks, Building Materials and Structures Reports, and Miscellaneous Publications.

Information on the Bureau’s publications can be found in

NBS Circular 460, Publications of the National Bureau of Standards

($1.00). Information on calibration services and fees can be found

in NBS Circular 483, Testing by the National Bureau of Standards

(25 cents). Both are available from the Government Printing Of fice

Inquiries regarding the Bureau’s reports and publications should be

addressed to the Office of Scientific Publications, National Bureau

of Standards, Washington 25, D. C.