# Bandwidth of a matrix

A band matrix is a matrix whose non-zero entries fall within a diagonal band, consisting of the main diagonal and zero or more diagonals on either side of it. (The main diagonal of a matrix consists of all entries $$\a_{i,j}\$$ for which $$\i=j\$$.) For this challenge, we will only be considering square matrices.

For example, given this matrix:

1 2 0 0
3 4 5 0
0 6 0 7
0 0 8 9


this is the band:

1 2
3 4 5
6 0 7
8 9


The main diagonal (1 4 0 9) and the diagonals above it (2 5 7) and below it (3 6 8) are the only places non-zero elements are found; all other elements are zero. (Some of the elements in the band may also be zero.)

The bandwidth of the matrix is the smallest number $$\k\$$ such that all non-zero elements are contained within a band consisting of the main diagonal, $$\k\$$ diagonals above it, and $$\k\$$ diagonals below it. The bandwidth of the above matrix is 1: all non-zero elements fall within the main diagonal, the one diagonal above it, or the one diagonal below it. For another example:

1 1 0 0
1 1 1 0
1 1 1 1
0 1 1 1


The bandwidth of this matrix is 2, because it takes two diagonals above and below the main diagonal to catch all non-zero elements:

1 1 0
1 1 1 0
1 1 1 1
1 1 1


Note that for the purposes of this challenge, the band must extend the same distance on either side of the main diagonal, which is why the diagonal 0 0 is included above.

Mathematically, the bandwidth is the smallest number $$\k\$$ such that for every entry $$\a_{i,j}\$$ in the matrix, $$\a_{i,j} = 0\$$ if $$\|i-j|>k\$$.

## Challenge

Given a square matrix containing nonnegative integers, output its bandwidth.

The matrix will always have at least one nonzero entry.

This is : make your code (measured in bytes) as short as possible.

## Test cases

1
=>
0

1 0 0
0 1 0
0 0 1
=>
0

1 2 0 0
3 4 5 0
0 6 0 7
0 0 8 9
=>
1

1 1 0 0
1 1 1 0
1 1 1 1
0 1 1 1
=>
2

16 18  8
6 14 22
20 10 12
=>
2

0 0 0 1 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
=>
3

• This makes the bandwidth of the zero matrix undefined, which I found sad as it could be with a better definition.
– YSC
Commented Feb 27, 2022 at 14:35
• @YSC Hmm, what definition would you propose? Commented Feb 28, 2022 at 18:17
• This is probably too late, and this won't add much to this challenge anyway. If I had to define that bandwidth, I'd make it so bandwidth(Zero)=0, bandwidth(Identity)=1.
– YSC
Commented Mar 1, 2022 at 9:01
• Ah, I see. I went by the definition on the Wikipedia article, which I assume is the official definition. I think if I were going to define something called bandwidth, it would be the actual width of the band (i.e. 2*k+1 if k is the bandwidth by this definition). ¯\_(ツ)_/¯ Commented Mar 1, 2022 at 16:43
• I'd say you were right to go with Wikipedia's definition rather than one from an unknown person on the Internet ^^
– YSC
Commented Mar 1, 2022 at 16:57

# Jelly, 5 bytes

ŒṪIAṀ


Try it online!

ŒṪ     -- indices of non-zero values
I    -- reduce each index by subtraction
A   -- get the absolute values
Ṁ  -- select the maximum


# R, 38 bytes

function(A)max(abs(row(A)-col(A))*!!A)


Try it online!

Test harness taken from Robin Ryder's answer.

R has some weird built-ins. Given a matrix M, row will return a matrix of the same size with each entry equal to its row number, and col likewise, but with columns. That is, $$\row(M)_{ij}=i\$$ and $$\col(M)_{ij}=j\$$. So abs(row(A)-col(A)) gives us a matrix of possible bandwidths like so for a $$\5\times 5\$$ matrix:

     [,1] [,2] [,3] [,4] [,5]
[1,]    0    1    2    3    4
[2,]    1    0    1    2    3
[3,]    2    1    0    1    2
[4,]    3    2    1    0    1
[5,]    4    3    2    1    0


Then we "filter" the entries where A is nonzero and take the maximum to obtain the bandwidth.

# R, 41 40 bytes

-1 byte thanks to Giuseppe

function(A)max(diff(t(which(t(A)|A,T))))


Try it online!

Note that the matrix $$\A|A^T\$$ has the same bandwidth as the matrix $$\A\$$, but is symmetrical. We can therefore consider only its lower-triangular part, for which row index is greater than column index.

The formula given in the question is $$\\max(|i-j|)\$$ such that $$\A_{ij}\neq 0\$$; this is equivalent to $$\\max(i-j)\$$ such that $$\(A|A^T)_{ij}\neq 0\$$ (without the absolute value). The call which(x,T) returns a 2-column matrix listing the row and column indices of all TRUE values in x; we need to transpose the output since diff acts column-wise.

This saves 3 bytes compared to the more obvious strategy:

function(A)max(abs(which(!!A,T)%*%c(1,-1)))


Edit: Outgolfed by Giuseppe's 38 byte answer.

• 40 bytes Commented Feb 27, 2022 at 17:47
• @Giuseppe Nice, thanks! Commented Feb 27, 2022 at 22:54
• 38 bytes Commented Feb 28, 2022 at 18:27
• @Giuseppe That's very different and much better, you should post it separately. I didn't know about the row and col functions! Commented Feb 28, 2022 at 19:51

# Python 3, 68 bytes

lambda a,e=enumerate:max(abs(i-j)for i,r in e(a)for j,c in e(r)if c)


Try it online!

Finds the largest $$\|i-j|\$$ among all entries $$\a_{ij} \neq 0\$$.

# Charcoal, 13 bytes

Ｉ⌈ＥＡ⌈Ｅι∧λ↔⁻μκ


Try it online! Link is to verbose version of code. Explanation:

   Ａ            Input array
Ｅ             Map over rows
ι         Current row
Ｅ          Map over elements
λ       Current element
∧        Logical And
μ    Column index
⁻     Subtract
κ   Row index
↔      Absolute value
⌈           Take the maximum
⌈              Take the maximum
Ｉ               Cast to string
Implicitly print


# MATL, 10 6 bytes

&f-|X>


Try it online!

Port of @ovs's Jelly solution.

(-4 bytes thanks to @LuisMendo)

Older

### MATL, 16 bytes

&+t"tX@&Rs~?X@q.


Outputs a transformed version of the input (input + input's transpose) and then the bandwidth. Not sure if extraneous output like this is usually allowed; if not, the "cleaner" version is just 1 byte longer: &+XH"HX@&Rs~?X@q. Try it out

• @LuisMendo I see them (ovs's and Lynn's methods) as pretty much the same thing? The trouble is getting the $i$ and $j$, half of the bytes are spent in ind2sub to get them. Commented Feb 27, 2022 at 0:05
• @LuisMendo :facepalm: I literally checked f's alternate specification when I read your (original) comment, but for some reason was looking at the input spec and thought there's no & form at all. Thanks! Commented Feb 27, 2022 at 0:09

# Pari/GP, 50 bytes

a->m=0;matrix(#a,,i,j,a[i,j]&&m=max(m,abs(i-j)));m


Try it online!

# J, 38 31 23 bytes

>./@,@(~:&0*|@-/~@i.@#)


-7 bytes by removing some useless parentheses
-8 bytes, thanks @ovs (see comment below)

Try it online!

• Both @,&0 and the parentheses around -/~ can be removed. You might also want to look at an arithmetic based way to do ~:&0#"1 (setting values to zero would have the same effect as removing them)
– ovs
Commented Feb 27, 2022 at 9:24
• @ovs Whoops, i got it, thanks! Commented Feb 27, 2022 at 12:10

# JavaScript (Node.js), 63 bytes

x=>x.map((r,i)=>r.map((c,j)=>v=c?Math.max(i-j,j-i,v):v),v=0)&&v


Try it online!

# JavaScript (ES7),  58  55 bytes

m=>m.map(q=(r,y)=>r.map(v=>q=!v|(n=y*y--)<q?q:n))|q**.5


Try it online!

# 05AB1E, 9 bytes

ĀDƶsøƶøαà


(Or ø‚Ā€ƶøαà as minor alternative.)

Explanation:

Ā        # Transform each non-0 integer in the input-matrix to a 1
D       # Duplicate this matrix of 0s/1s
ƶ      # Multiply each inner value by its 1-based row-index
s       # Swap so the matrix of 0s/1s is at the top again
øƶø    # Do the same for the columns
# (where ø is a zip/transpose, to swap rows/columns)
α   # Take the absolute difference of the values at the same positions
à  # Pop and push the flattened maximum
# (which is output implicitly as result)


# VyxalG, 7 bytes

vT:ẏ-ȧf


vT:ẏ-ȧf
`