File Exchange

## Circulant matrix

version 1.2 (2.87 KB) by

The circulant matrix generated from a vector as the first row (or first column)

Updated

A circulant matrix is a square matrix generated from a vector as the first row (or column). Successive rows use the same elements as the first row, but each such row is circularly shifted by one element. See that both Wikipedia and Mathworld show the circular shifts as forward shifts.

http://en.wikipedia.org/wiki/Circulant_matrix

http://mathworld.wolfram.com/CirculantMatrix.html

At the same time, others seem to employ backwards shifts (see FEX 22814), so there is clearly a dichotomy in the set of people who use circulant matrices. I'll offer my own version of circulant.m to cover either style. It allows the user to specify either form as desired, although the default uses the forwards shift. For example:

A backwards (-1) shift, the result is a symmetric matrix.

circulant([2 3 5 7 11 13],-1)

ans =
2 3 5 7 11 13
3 5 7 11 13 2
5 7 11 13 2 3
7 11 13 2 3 5
11 13 2 3 5 7
13 2 3 5 7 11

A forwards (+1) shifted circulant matrix, built using the first row defined by vec.

circulant([2 3 5 7 11],1)

ans =
2 3 5 7 11
11 2 3 5 7
7 11 2 3 5
5 7 11 2 3
3 5 7 11 2

And a positively shifted circulant matrix, built from vec as the first column. Here I've provided only one argument, so it uses the default.

circulant([2;3;5;7;11])
ans =
2 11 7 5 3
3 2 11 7 5
5 3 2 11 7
7 5 3 2 11
11 7 5 3 2

Finally, a negative shift applied to build a character circulant matrix.

circulant('abcdefghij',-1)

ans =
abcdefghij
bcdefghija
cdefghijab
defghijabc
efghijabcd
fghijabcde
ghijabcdef
hijabcdefg
ijabcdefgh
jabcdefghi

Finally, I'll note that the algorithms I chose internally are not absolutely the fastest, although they are fully vectorized. I could have achieved a further 10-20% speed boost with the use of bsxfun. The code for the bsxfun variants is included, but commented out. The problem is that many people still have not upgraded to a release that includes bsxfun. While I could have put in a test to see if bsxfun exists, that test itself takes some time since exist is relatively slow. On small vectors, the test itself might take more time than it takes to generate the matrix.

So for any user who has bsxfun and needs maximal throughput, I've put it all in there for you.

John D'Errico

### John D'Errico (view profile)

Why not? A good question, but it shows that you have not tried it, or seriously tested it, or even looked at the help.

My circulant code is FASTER than the gallery code. So why would you use (or recommend) a slower solution?

>> c = 1:100;
>> timeit(@() gallery('circul',c))
ans =
4.6459e-04

>> timeit(@() circulant(c))
ans =
2.5056e-04

Next, circulant is CONSIDERABLY more flexible than the gallery trick, allowing you to build a variety of related matrices. So use a tool that is flexible, is fast, AND has good help. All of that suggests use of this tool.

I could have written circulant as a wrapper for the gallery trick, but why?

Richard Zapor

### Richard Zapor (view profile)

Why not use R2012B

gallery('circul',c)'; ?

Lutful Nishan

### Lutful Nishan (view profile)

Hey John,
I think I figured it out myself, the function was in the download file link.
Thanks Anyways

Lutful Nishan

### Lutful Nishan (view profile)

Hi John,
I am new to matlab, so sorry for asking such stupid question.
Did you create a function for circulant? or was it a library call?
Because when I copy paste circulant([2;3;5;7;11]) or our other commands in matlab I receive error.
Thanks in advance for helping.

John D'Errico

### John D'Errico (view profile)

us is right. Duane sent me his revision, and I was lazy, just submitting it essentially as he wrote it, only acknowledging his effort on the website. I'll revise that now.

us

### us (view profile)

dear john,
in your 'updates' note you tell the community that duane has substantially added to the help section of your already great submission...
however, if i look at the revised code, i do not see any acknowledgement of his effort embedded in the code...
appreciating you as an academically very honest author, i am sure this is just a temporary mishap...
us

Jos (10584)

### Jos (10584) (view profile)

This well-written function inspired me to submit my own version that uses simple matrix operations which should be up soon. Well done John and thanks for the inspiration.

John D'Errico

### John D'Errico (view profile)

I agree with Duane. He offered a help block that was cleaner, and far less verbose, so the new version I just put up has his help. My thanks.

Duane Hanselman

### Duane Hanselman (view profile)

Other than having non MATLAB standard help text formatting, this does everything one could ask for and more.

John D'Errico

### John D'Errico (view profile)

Husam asks a good question. I considered a try/catch construct, as well as just a test against exist('bsxfun'). The thing is, the alternative was fast enough that bsxfun does not give a terribly significant speed gain. For reasonably small matrices, a simple test for bsxfun may cost as much time as creating the entire matrix. Even for larger matrices, the time penalty did not seem excessive for avoiding bsxfun here. As I suggest, for someone who needs to truly maximize speed, they will not want to pay any additional time penalty.

I'll look at try/catch to see if it costs less than exist. If not, in a year or so, most of the matlab base will have moved to a release that includes bsxfun, so I'll look to change the code then.

Husam Aldahiyat

### Husam Aldahiyat (view profile)

Why no use try/catch for the bsxfun thing?

us

### us (view profile)

a long overdue function with excellent help and examples as well as a clean computational engine including copious comments...
what else...
us